429. Merge Two Binary Trees
You are given the roots of two binary trees, root1 and root2. Imagine sliding one tree on top of the other so their roots line up. Some positions now hold a node from both trees; others hold a node from only one.
Build the merged tree by this rule: where both trees have a node, the merged node's value is the sum of the two values; where only one tree has a node, that node — together with its whole subtree — is used as-is.
Return the root of the merged tree. Either input tree may be empty.
Example 1:
Input: root1 = [1, 2, 4, 7], root2 = [3, 6, 5, null, 9, 8]
Output: [4, 8, 9, 7, 9, 8]
Explanation: The roots overlap (1 + 3 = 4), both left children overlap (2 + 6 = 8), and both right children overlap (4 + 5 = 9). Node 7 exists only in tree 1, and nodes 9 and 8 exist only in tree 2, so they are carried over unchanged.
Example 2:
Input: root1 = [], root2 = [5, 2]
Output: [5, 2]
Explanation: Tree 1 is empty, so the merged tree is exactly tree 2.
Constraints:
- Each tree has between 0 and 2000 nodes.
- -10⁴ ≤ Node.val ≤ 10⁴
Hints:
Process the two trees together, one position at a time: a call receives one node from each tree (either of which may be missing).
If one of the two nodes is missing, you are done at that position — the other node's entire subtree is the answer there, no copying needed.
When both nodes exist, sum them, then recurse on the two left children and the two right children.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root1 = [1, 2, 4, 7], root2 = [3, 6, 5, null, 9, 8]
Expected output: [4, 8, 9, 7, 9, 8]