Remove Subtrees From Parent Array
MediumTrees ยท Pinterest
Given a forest as an array parent, where parent[i] is the parent of node i and -1 marks a root, remove every node in targets together with all of its descendants.
Return the parent array of the remaining nodes. Nodes are renumbered 0, 1, 2, ... in the order of their original indices, each parent value is rewritten to its parent's new number, and roots stay -1.
A parent can have a larger index than its child. targets may repeat nodes or name nodes already inside another target's subtree.
Example 1
- Input:
- parent = [-1, 0, 0, 1, 1, 2], targets = [1]
- Output:
- [-1, 0, 1]
- Explanation
- Removing node 1 also removes 3 and 4. Nodes 0, 2, 5 become 0, 1, 2, and node 5's parent 2 becomes 1.
Example 2
- Input:
- parent = [2, 2, -1, 0, 3, -1], targets = [0]
- Output:
- [1, -1, -1]
Example 3
- Input:
- parent = [-1, -1, 1, 0], targets = [1, 3]
- Output:
- [-1]
Constraints
0 <= parent.length <= 10^5parent[i] == -1or0 <= parent[i] < parent.lengthwithparent[i] != i, and the array has no cycles0 <= targets.length <= parent.length0 <= targets[j] < parent.length