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.
1public class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode() {}
6 TreeNode(int val) { this.val = val; }
7 TreeNode(int val, TreeNode left, TreeNode right) {
8 this.val = val;
9 this.left = left;
10 this.right = right;
11 }
12}
13
14class Solution {
15 public TreeNode pruneTree(TreeNode root) {
16 if (root == null) {
17 return null;
18 }
19 root.left = pruneTree(root.left);
20 root.right = pruneTree(root.right);
21 if (root.val == 0 && root.left == null && root.right == null) {
22 return null;
23 }
24 return root;
25 }
26}The Java solution uses a recursive function that works post-order. It starts by pruning the root's left and right children and then checks if both have been reduced to NULL alongside a value of 0 within the root. Such nodes and subtrees get pruned. The recursion ensures the final tree returned contains only subtrees with a 1.
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.
1
The C implementation employs a boolean helper function, containsOne, which verifies if any subtree contains the value 1. The iterative sense is simulated by the helper function instead of explicit stack management. Nodes without 1 in their subtrees are trimmed, promoting a structured pruning process.