LeetCode 814: Binary Tree Pruning

Explanation

To solve this problem, we can perform a post-order traversal of the tree. At each node, we recursively check the left and right subtrees. If both subtrees do not contain any 1, and the current node also does not have a value of 1, we can prune the subtree rooted at the current node by returning null. Otherwise, we return the current node.

Algorithm

1. Recursively prune the left subtree.
2. Recursively prune the right subtree.
3. Check if the current node is a leaf and has a value of 0, prune it by returning null.
4. Return the current node.

Time Complexity

The time complexity of this approach is O(N), where N is the number of nodes in the tree. We visit each node once during the post-order traversal.

Space Complexity

The space complexity is also O(N) due to the recursive calls on the stack.

class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if (root == null) return null;
        
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        
        if (root.left == null && root.right == null && root.val == 0) {
            return null;
        }
        
        return root;
    }
}