Preorder Traversal of a Parsed N-ary Tree
Problem statement
You are given records describing a tree in which each node may have any number of children. Parse the records and return the node IDs in preorder: visit a node before visiting its children from left to right.
Each record has the exact form id:child1,child2,...; a leaf is id:. IDs are nonnegative integers written in decimal, with no extra spaces or leading zeros except for zero itself. The first record identifies the root. Remaining records may appear in any order. A record’s child list defines left-to-right order.
Every ID has exactly one record, each referenced child exists, and the records form one valid connected tree. Return an empty array for an empty record list. Parse the records and build the tree before traversing; the record-list order is not the traversal order.
Function
preorder(records: String[]) → int[]Examples
Example 1
records = ["10:20,30","30:40","20:","40:"]return = [10,20,30,40]Child 20 precedes child 30 even though their records are listed in the opposite order.
Example 2
records = ["5:9,1,7","7:","1:3","9:","3:"]return = [5,9,1,3,7]After visiting 9, traverse the entire subtree of 1 before sibling 7.
Example 3
records = []return = []An empty list describes an empty tree.
Constraints
0 <= records.length <= 2000.- Node IDs are in
0..1000000000; the total record length is at most50000characters. - Every record follows the stated grammar and the records form a valid tree.