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.
1function TreeNode(val, left, right) {
2 this.val = (val===undefined ? 0 : val)
3 this.left = (left===undefined ? null : left)
4 this.right = (right===undefined ? null : right)
5}
6
7var pruneTree = function(root) {
8 if (!root) return null;
9 root.left = pruneTree(root.left);
10 root.right = pruneTree(root.right);
11 if (root.val === 0 && !root.left && !root.right) return null;
12 return root;
13};This JavaScript implementation handles a binary tree pruning through post-order recursion. Each subtree gets evaluated recursively; if no 1 exists in a subtree, or if part of the subtree contains just nodes with a value of 0, such nodes get pruned by setting their references to null. This tidy approach ensures efficient maintenance of necessary nodes.
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.
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode PruneTree(TreeNode root) {
if (root == null) return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
TreeNode prev = null;
while (stack.Count > 0) {
TreeNode node = stack.Peek();
if ((node.left == null && node.right == null) || node.left == prev || node.right == prev) {
if (node.val == 0 && node.left == null && node.right == null) {
if (node == root) return null;
if (prev == node.left) node.left = null;
if (prev == node.right) node.right = null;
}
prev = node;
stack.Pop();
} else {
if (node.right != null) stack.Push(node.right);
if (node.left != null) stack.Push(node.left);
}
}
return root.val == 0 && root.left == null && root.right == null ? null : root;
}
}The C# code implements iterative traversal via a user-implemented stack. This approach delegates recursion to the call stack, avoiding default recursive stack utility, proceeds through managing node manipulation based on subtree data.