Flatten a Branched List into a Doubly Linked List
Tesla● MediumFULLTIMEPHONE SCREENProblem statement
A branched list contains n nodes. Node i stores values[i], may point to a next node through nextIndices[i], and may point to one side branch through branchIndices[i]. A value of -1 means that pointer is absent.
Flatten the structure in preorder: visit a node, then its entire side branch, then the node's original next chain. Convert that order into one doubly linked list.
Return one row per flattened position. Row i is [value, previousPosition, nextPosition], where missing neighbors are encoded as -1.
Function
flattenBranchedList(values: int[], nextIndices: int[], branchIndices: int[], headIndex: int) → int[][]Examples
Example 1
values = [1,2,3,4,5]nextIndices = [1,2,-1,4,-1]branchIndices = [-1,3,-1,-1,-1]headIndex = 0return = [[1,-1,1],[2,0,2],[4,1,3],[5,2,4],[3,3,-1]]The branch rooted at node 3 is inserted after node 1 and before its original next node 2.
Example 2
values = [7]nextIndices = [-1]branchIndices = [-1]headIndex = 0return = [[7,-1,-1]]A single node has neither a previous nor a next flattened neighbor.
Example 3
values = [10,20,30,40]nextIndices = [1,-1,-1,-1]branchIndices = [2,-1,3,-1]headIndex = 0return = [[10,-1,1],[30,0,2],[40,1,3],[20,2,-1]]Nested side branches are completed before traversal resumes along an original next pointer.
Constraints
1 <= n <= 100000.values.length = nextIndices.length = branchIndices.length = n.- Each pointer is
-1or a valid node index. - The nodes reachable from
headIndexform an acyclic branched list, and every reachable node is visited exactly once. -10^9 <= values[i] <= 10^9.