1043. Prune to a Forest
A shared drive stores folders as a binary tree rooted at root; every folder carries a unique numeric id in its val field. The ids listed in toDelete are being removed. When a folder disappears, the folders directly under it are not deleted along with it: each of them simply becomes the top folder of its own separate tree.
Remove every node whose value appears in toDelete and return the roots of all trees that remain, in any order. Ids in toDelete that are not in the tree are ignored, and if nothing remains the result is empty. Unaffected parent-child links must stay exactly as they were.
Aim for O(n) time; avoid recursion that could be as deep as the tree is tall.
Example 1
- Input:
- root = [1,2,3,4,5,6,7], toDelete = [3,5]
- Output:
- [[1,2,null,4],[6],[7]]
- Explanation:
Removing 3 and 5 leaves root 1 (keeping 2 and 4), and the children 6 and 7 of the removed 3 become two single-node trees.
Example 2
- Input:
- root = [1,2,null,3,null,4], toDelete = [2]
- Output:
- [[1],[3,4]]
- Explanation:
Removing 2 splits the chain: 1 stays alone and 3 becomes a new root that still holds 4.
Example 3
- Input:
- root = [5,3,8], toDelete = [5,9]
- Output:
- [[3],[8]]
- Explanation:
The root 5 is removed, so 3 and 8 become separate trees; 9 is not in the tree and is ignored.
Constraints
1 ≤ number of nodes ≤ 2 * 104.
Node values are distinct integers with 1 ≤ val ≤ 109.
0 ≤ toDelete.length ≤ 2 * 104, and its values are distinct.
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
Expected complexity
- Time
- O(n)
- Space
- O(n)