Merge Two Binary Trees

Path Sum II

Binary Tree Right Side View

Overlay two binary trees, summing values where both nodes exist and keeping whichever node exists otherwise.

You are given the roots of two binary trees `t1` and `t2`.

Imagine that when you overlay one tree on top of the other, some nodes of the two trees line up while others do not. Merge the two trees into a new binary tree: if two nodes overlap, the new node's value is the sum of both nodes' values; otherwise the non-null node becomes the new tree's node.

Return the merged tree's root.

**Input / output**
- Input: `t1: TreeNode`, `t2: TreeNode` (JSON test fixtures are LeetCode-style level-order arrays, e.g. `[1,3,2,5]`, with `null` for a missing child)
- Output: `TreeNode` (also a level-order array)

## Example
```json
Input: {"t1":[1,3,2,5],"t2":[2,1,3,null,4,null,7]}
Output: [3,4,5,5,4,null,7]
```

## Constraints
- 0 <= number of nodes in each tree <= 2,000
- -10,000 <= node value <= 10,000

## Follow-up
Can you merge the trees in place, mutating `t1` to become the merged result instead of allocating new nodes?

The key pattern is: synchronized preorder recursion over two trees at once, where a missing node on either side contributes 0 and an empty subtree on both sides ends the recursion.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

Check Edge Cases

Time: O(min(m, n)) — recursion only descends as long as at least one of the two trees still has a node at that position; m and n are the node counts of t1 and t2. Space: O(min(m, n)) for the recursion stack in the worst case (skewed trees).

All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real TreeNode structural-type support the judge added for the rest of the linked-list/tree track.