Merge Two N-ary Trees by Matching Node Keys

You are given two rooted n-ary trees in which every node carries an integer key. Merge them by key: a node of the first tree and a node of the second tree are combined into a single node only when they have the same key **and** occupy the same position, meaning both are roots, or they are children of two nodes that were themselves combined. A node with no partner in the other tree is copied into the result unchanged, together with its whole subtree. Each tree is given as a flat list of rows `[key, parent]`, and the merged tree is returned in the same form, listed in the fixed preorder described under Rules. ### Function Signature ```python def merge_trees_by_key(tree1: list[list[int]], tree2: list[list[int]]) -> list[list[int]]: ``` ### Rules - **Input encoding.** Row `i` of a tree is `[key, parent]`. Row `0` is the root, and its parent is `-1`. Every other row has `0 <= parent < i`, the index of its parent's row. The children of a node are ordered by increasing row index. An empty list is an empty tree. - **Roots.** If both trees are non-empty and their root keys differ, the trees cannot be merged: return `[]`. - **Empty trees.** If exactly one tree is empty, the result is the other tree, re-encoded as described below. If both are empty, return `[]`. - **Combining two nodes.** When node `u` of `tree1` is combined with node `v` of `tree2`, the result node has their shared key, and its children are, in this order: 1. each child of `u`, in `u`'s order, combined with the child of `v` that has the same key if there is one, and otherwise copied with its subtree; 2. then each child of `v` whose key matches no child of `u`, in `v`'s order, copied with its subtree. - A copied subtree keeps the child order it had in its own tree. - **Output encoding.** List the merged tree's nodes in preorder: a node first, then the subtrees of its children in the child order above. Each output row is `[key, parent]`, where `parent` is the index of the parent's row in the output list, and `-1` for the root. This makes the result unique. ### Constraints - `0 <= len(tree1) <= 10^4` and `0 <= len(tree2) <= 10^4` - `-10^9 <= key <= 10^9` - Row `0` of a non-empty tree has parent `-1`; every row `i >= 1` has `0 <= parent < i`. - Within one tree, the children of any single node have pairwise distinct keys. The same key may appear elsewhere in the tree, under a different parent or at a different depth. - Every root-to-leaf path in each tree has at most 500 nodes. ### Examples **Example 1** - Input: `tree1 = [[1, -1], [2, 0], [3, 0], [4, 1]]`, `tree2 = [[1, -1], [3, 0], [5, 0], [6, 1], [7, 2]]` - Output: `[[1, -1], [2, 0], [4, 1], [3, 0], [6, 3], [5, 0], [7, 5]]` - Explanation: Both roots have key `1` and are combined. The root's children are `2` (only in `tree1`, copied with its child `4`), then `3` (in both trees, combined; it gains the child `6` from `tree2`), then `5` (only in `tree2`, copied with its child `7`). The preorder listing is `1, 2, 4, 3, 6, 5, 7`. **Example 2** - Input: `tree1 = [[1, -1], [2, 0]]`, `tree2 = [[9, -1], [2, 0]]` - Output: `[]` - Explanation: The root keys `1` and `9` differ, so the trees cannot be merged. **Example 3** - Input: `tree1 = [[5, -1], [8, 0], [2, 0], [8, 2]]`, `tree2 = [[5, -1], [2, 0], [8, 0], [8, 1], [3, 1]]` - Output: `[[5, -1], [8, 0], [2, 0], [8, 2], [3, 2]]` - Explanation: The root's children follow `tree1`'s order, `8` then `2`, and each is combined with its partner in `tree2`. Under `2`, the child `8` is combined and the child `3` is added from `tree2`. The key `8` appears at two depths, but a node is only combined with the `8` under the matching parent.