Sponsored
Sponsored
This approach uses a tree traversal technique, specifically post-order traversal, to manage the deletion process. By performing the traversal from the leaves to the root, you can easily detach the nodes that need to be deleted. Each subtree that gets detached as a result of deleting a node potentially becomes a representative of a new tree in the forest.
Time Complexity: O(N), as each node is visited once.
Space Complexity: O(N), accounting for the implicit space used by the recursive stack.
1class Solution:
2 def delNodes(self, root, to_delete):
3 to_delete_set = set(to_delete)
4 res = []
5
6 def helper(node, is_root):
7 if not node:
8 return None
9 root_deleted = node.val in to_delete_set
10 if is_root and not root_deleted:
11 res.append(node)
12 node.left = helper(node.left, root_deleted)
13 node.right = helper(node.right, root_deleted)
14 return None if root_deleted else node
15
16 helper(root, True)
17 return resThe solution uses a nested function helper that recursively traverses the tree in a post-order fashion. Inside the helper, it checks if the current node should be deleted. If it's a root node of a new tree and not deleted, it is added to the result list. Each child node is checked in a similar manner, ensuring that disconnected subtrees form new roots if they're not in the delete set.
This approach involves using a breadth-first search (BFS) paradigm that keeps track of each node's parent. When we encounter a node that is to be deleted, we modify the parent's pointer to null, effectively removing the node. At the same time, if this deleted node has children, they become new tree roots if they are not included in the deletion list.
Time Complexity: O(N), as all nodes are processed individually.
Space Complexity: O(N), since the queue can hold at most all nodes plus necessary supporting storage like HashSet.
1class Solution {
2 public ListThe Java solution uses a queue to traverse the tree in a level-order manner. For each node processed, it checks if the node's children need deletion. If so, it ensures the respective children are handled (either added to the result as new roots or their pointers reset). The traversal ensures all deletions are effectively managed within a single pass through the tree.