Sponsored
Sponsored
This approach uses post-order traversal to traverse each subtree and decide if it should be pruned. Starting from the leaf nodes, it recursively checks if a subtree contains a 1. If a subtree doesn't contain any 1s, it returns null. This way, when the recursion unwinds, only relevant subtrees are kept.
Time Complexity: O(N), where N is the number of nodes, since each node is visited once.
Space Complexity: O(H), where H is the height of the tree, due to the recursive stack space.
1#include <queue>
2#include <cmath>
3
4class TreeNode {
5public:
6 int val;
7 TreeNode* left;
8 TreeNode* right;
9 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
10};
11
12TreeNode* pruneTree(TreeNode* root) {
13 if (!root) return nullptr;
14 root->left = pruneTree(root->left);
15 root->right = pruneTree(root->right);
16 if (root->val == 0 && !root->left && !root->right) return nullptr;
17 return root;
18}The C++ solution adopts a post-order traversal approach using recursion. For each node, it first prunes its left and right children. If both children are pruned (returned as NULL) and the node's value is 0, the current node also gets pruned by returning NULL. Otherwise, it keeps the node, ensuring all necessary subtrees are maintained.
By utilizing an iterative traversal using a stack, the tree can be pruned without recursion. This approach mimics the recursion stack by using an explicit stack to manage nodes that need to be processed. Once the subtree rooted at a node is evaluated, decisions are made to prune or retain nodes based on whether a 1 is found.
Time Complexity: O(N), as we are ensuring every node is visited.
Space Complexity: O(H), attributed to the height of the tree in terms of stack use.
This iterative Java solution appropriates a stack to simulate post-order traversal and manage node removal without recursion. The algorithm tracks node processing and manipulation status for subtrees under circumstances that require pruning efficiently.