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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def pruneTree(self, root: TreeNode) -> TreeNode:
9 if not root:
10 return None
11 root.left = self.pruneTree(root.left)
12 root.right = self.pruneTree(root.right)
13 if root.val == 0 and not root.left and not root.right:
14 return None
15 return rootThe Python solution implements a recursive pruning routine. It performs a post-order traversal by first addressing the left and right subtrees. Nodes rendering left and right subtrees to None and having a value of 0 are also pruned by return of None. This approach ensures robustness in retaining only necessary sections of the tree.
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.
Employing manual stack management, this Python implementation executes an iterative approach to pruning, circumventing recursive call overheads. Nodes are investigated post-order, determining prunability by contextual subtree status, assuring comprehensive solution application.