Given the root of a binary tree, each node in the tree has a distinct value.
After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).
Return the roots of the trees in the remaining forest. You may return the result in any order.
Example 1:
Input: root = [1,2,3,4,5,6,7], to_delete = [3,5] Output: [[1,2,null,4],[6],[7]]
Example 2:
Input: root = [1,2,4,null,3], to_delete = [3] Output: [[1,2,4]]
Constraints:
1000.1 and 1000.to_delete.length <= 1000to_delete contains distinct values between 1 and 1000.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.
The 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.
JavaScript
Time Complexity: O(N), as each node is visited once.
Space Complexity: O(N), accounting for the implicit space used by the recursive stack.
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.
The 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.
C#
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.
| Approach | Complexity |
|---|---|
| Approach 1: Post-order Traversal | Time Complexity: O(N), as each node is visited once. |
| Approach 2: BFS with Parent References | Time Complexity: O(N), as all nodes are processed individually. |
Delete Nodes and Return Forest • Kevin Naughton Jr. • 31,282 views views
Watch 9 more video solutions →Practice Delete Nodes And Return Forest with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor