Merge Folder Trees
MediumTrees ยท LinkedIn
Two folder trees are given as lists a and b of [name, parent] entries in preorder. Entry i is a folder called name inside the folder at index parent, and the root has parent -1. Folders inside one folder have distinct names.
If the roots have different names, return []. Otherwise merge b into a: folders with the same name inside the same merged folder become one, recursively. Inside each merged folder, the folders from a come first in their original order, then the folders only in b in their original order. Return the merged tree in the same encoding.
Example 1
- Input:
- a = [["src", -1], ["lib", 0], ["util", 1], ["app", 0]], b = [["src", -1], ["app", 0], ["main", 1], ["lib", 0], ["util", 3], ["io", 3], ["test", 0]]
- Output:
- [["src", -1], ["lib", 0], ["util", 1], ["io", 1], ["app", 0], ["main", 4], ["test", 0]]
- Explanation
libandappexist in both trees, so they merge and keepa's order.ioandmainare added inside them;testcomes last.
Example 2
- Input:
- a = [["src", -1], ["lib", 0]], b = [["source", -1], ["lib", 0]]
- Output:
- []
Example 3
- Input:
- a = [["src", -1], ["lib", 0], ["util", 1]], b = [["src", -1], ["util", 0]]
- Output:
- [["src", -1], ["lib", 0], ["util", 1], ["util", 0]]
- Explanation
- The two
utilfolders sit in different parents, so they stay separate.
Constraints
1 <= a.length, b.length <= 10^5nameis a non-empty string of at most 10 characters- Each list is a valid preorder encoding of a tree:
parentis the index of an earlier entry, and the first entry has parent-1