Flatten and Reconstruct an Ordered Tree
Problem statement
Flatten an ordered tree into a structure-preserving sequence, or reconstruct the tree from that sequence. The tree may have any number of children per node and may contain duplicate values.
For this exercise, mode=0 encodes a tree. Input row i is [parentIndex,value]. The root has parent -1; a parent may appear before or after its child in the input. Children of each parent are ordered by increasing input row index. Return preorder rows [value,childCount], visiting a node before its children from first to last.
mode=1 decodes a valid preorder sequence of [value,childCount] rows. Return [parentIndex,value] records in preorder, using the output row indices as the new node numbers and -1 for the root. Preserve every node value, child relationship and sibling order. Original row numbers are serialization identifiers and are not recovered; reconstruction assigns new preorder numbers.
An empty tree is represented by an empty array in either direction. This ordered-tree model, traversal, child-count format and numbering rule are practice choices for the reported flatten-and-reconstruct pair.
Function
orderedTreeCodec(mode: int, records: int[][]) → int[][]Examples
Example 1
mode = 0records = [[2,20],[2,30],[-1,10],[0,40]]return = [[10,2],[20,1],[40,0],[30,0]]Input row 2 is root 10, whose children are rows 0 and 1 in that order. Node 20 has child 40. Preorder is 10,20,40,30, giving [[10,2],[20,1],[40,0],[30,0]].
Example 2
mode = 1records = [[7,2],[7,0],[9,1],[7,0]]return = [[-1,7],[0,7],[0,9],[2,7]]The first 7 is the root. Its first child is a leaf 7; its second child is 9 with one leaf 7. New preorder indices yield [[-1,7],[0,7],[0,9],[2,7]]. Repeated values remain separate nodes.
Constraints
0 <= mode <= 10 <= records.length <= 200records[i].length == 2-1000000 <= records[i][j] <= 1000000- For mode 0, nonempty records form one valid rooted tree: one parent -1, every other parent is a valid row index, and every node reaches the root without a cycle.
- For mode 1, nonempty records are a valid preorder encoding of exactly one tree, with nonnegative child counts less than records.length.