Delete Leaves With a Given Value

[ymolliks]

Ideas

1. Post-order Traversal

Solution

Just do a post-order traversal of the tree:

remove(root->left)
remove(root->right)
remove(root)

That is, from current node $\tt curr$ recursively go to the left subtree $\tt curr\rightarrow left$ and remove it if necessary, then recursively go to the right subtree $\tt curr\rightarrow right$ and remove it if necessary. And finally, if $\tt curr\rightarrow val$ equals to $\tt target$ and $\tt curr$ is/became a leaf, then delete $\tt curr$ too.

Implementation

class Solution {
public:
    TreeNode *removeLeafNodes(TreeNode *root, int target) {
        remove(root, target);
        return root;
    }

    void remove(TreeNode *&curr, int &target) {
        if (curr->left)
            remove(curr->left, target);
        if (curr->right)
            remove(curr->right, target);

        if (curr->val == target and !curr->left and !curr->right)
            curr = nullptr;
    }
};

Complexity

Time: $\tt O(n)$

Space: $\tt O(1)$

[ymolliks]

Delete Leaves With a Given Value