Merge two n-ary trees by child position

Implement merge_trees(root1, root2). It takes the roots of two n-ary trees and returns the root of a new tree that merges them.

Each node has an integer val and an ordered list children:

class TreeNode:
    val: int
    children: list[TreeNode]

Nodes are matched by position: the roots match, and the child at index i of a matched pair matches the child at index i of the other node.

• If both trees have a node at a position, the merged node's value is the sum of the two values.
• If only one tree has a node at a position, the merged tree contains a copy of that whole subtree.
• The result must not share any node objects with the inputs. Do not modify the inputs.

Either root may be None. If both are None, return None.

Constraints

• Each tree has 0 to 10^5 nodes, and a tree can be up to 10^5 levels deep.
• Node values are in [-10^4, 10^4].

Example 1

Tree A:        Tree B:
    1              2
   / \           / | \
  3   2         1  3  7
  |            / \    |
  5           4   6   8

Merged:
      3
   /  |  \
  4   5   7
 / \      |
9   6     8

The roots give 1 + 2 = 3. Child 0 gives 3 + 1 = 4, and its children give 5 + 4 = 9 and a copy of 6. Child 1 gives 2 + 3 = 5. Child 2 exists only in B, so its subtree 7 -> 8 is copied.

Example 2

merge_trees(None, TreeNode(4, [TreeNode(-1)])) returns a new tree 4 -> -1. Changing the result does not change the input tree.

Reconstructed from the reported question; details may differ from what interviewers ask.