Merge Hierarchical Trees by Name
Problem statement
Two ordered rooted trees are encoded by parallel names, values, and parents arrays. Nodes are listed in preorder. The root is index 0 with parent -1; each later parent index is smaller than its child index. Sibling order is their order in the arrays.
Merge the two roots. A merged node takes its name from the first tree and its value from the second tree. For each pair of merged parents, children with the same name are paired in occurrence order and merged recursively.
- Keep every child from the first tree in its original order.
- Copy an unmatched first-tree child with its complete subtree unchanged.
- After those children, append every unmatched second-tree child with its complete subtree in its original order.
Return the merged tree in preorder. Encode each node as depth:name:value, where the root depth is 0.
Function
mergeHierarchies(names1: String[], values1: int[], parents1: int[], names2: String[], values2: int[], parents2: int[]) → String[]Examples
Example 1
names1 = ["root","a","x","a"]values1 = [1,2,3,4]parents1 = [-1,0,1,0]names2 = ["other","a","y","a","z","b"]values2 = [10,20,30,40,50,60]parents2 = [-1,0,1,0,3,0]return = ["0:root:10","1:a:20","2:x:3","2:y:30","1:a:40","2:z:50","1:b:60"]The first and second a children pair by occurrence. Unmatched first-tree children remain before unmatched second-tree children, and the second-tree b child is appended last.
Example 2
names1 = ["r","left"]values1 = [1,2]parents1 = [-1,0]names2 = ["r2","right"]values2 = [9,8]parents2 = [-1,0]return = ["0:r:9","1:left:2","1:right:8"]The root uses the first root's name and second root's value. Its differently named children remain in first-tree then second-tree order.
Constraints
1 <= names1.length, names2.length <= 2000.- Within each tree, the three parallel arrays have equal lengths.
- Nodes are listed in preorder;
parents[0] == -1and0 <= parents[i] < ifori > 0. - Every name contains lowercase English letters, has length from
1through30, and contains no colon. - Node values fit in a signed 32-bit integer.
- Tree depth is at most
500.