hardTreesPure DSA~35 min
Delete Nodes and Return the Resulting Forest
Decommissioning certain nodes in a tree splits it into a forest. Delete every node whose id is in a removal set and return the roots of all remaining trees.
Problem
Given the root of a binary tree with distinct values and a list to_delete of values to remove, delete those nodes. The result is a forest of disjoint trees; return their roots in any order.
Input
A binary tree root and a list to_delete of values.
Output
A list of remaining tree roots.
Constraints
- 1 <= number of nodes <= 1000
- Each node has a distinct value in [1, 1000].
- to_delete contains distinct values.
Examples
Example 1
Input
root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output
[[1,2,null,4],[6],[7]]
Deleting 3 and 5 leaves three trees rooted at 1, 6, and 7.
Example 2
Input
root = [1,2,4,null,3], to_delete = [3]
Output
[[1,2,4]]
Deleting leaf 3 leaves one tree.