Delete Nodes and Return an N-ary Forest
Google● MediumFULLTIMEPHONE SCREENProblem statement
An N-ary tree has nodes numbered 0 through n - 1, with root 0. children[i] lists the children of node i in their original left-to-right order. Delete every node whose number appears in toDelete. A deleted node is removed, but each of its surviving children becomes the root of a separate tree unless another deleted node breaks that tree further.
Return the remaining forest as a two-dimensional array. Each inner array lists the nodes of one surviving tree in breadth-first order, following the original child order and skipping deleted nodes. Order the inner arrays by their root node number, smallest first. If no nodes survive, return an empty array.
Function
deleteNaryForest(children: int[][], toDelete: int[]) → int[][]Examples
Example 1
children = [[1,2,3],[4],[5,6],[],[],[],[]]toDelete = [1,2]return = [[0,3],[4],[5],[6]]Deleting 1 and 2 splits their surviving children into roots 4, 5, and 6; node 0 stays connected to 3.
Example 2
children = [[1,2],[3],[],[]]toDelete = [0,2]return = [[1,3]]The original root and node 2 are removed. The remaining tree is rooted at 1 and contains 3.
Example 3
children = [[]]toDelete = []return = [[0]]The single root survives as a one-node tree.
Example 4
children = [[1,2],[],[]]toDelete = [0,1,2]return = []Every node is deleted, so the forest is empty.
Constraints
1 <= children.length <= 1000.childrendescribes a valid tree rooted at0: every node except0appears in exactly one child list, no node is its own child, and all nodes are reachable from0.toDeletecontains distinct node numbers in[0, n - 1]and may be empty.