Lay one tree over the other
Merge two trees by adding values where both have a node and keeping whichever node exists elsewhere, by recursing on the matching positions. About 12 minutes.
Two trees, one position
Imagine placing one tree on top of the other so that roots line up, left children line up, and right children line up. Where both have a node, the merged node holds the sum of their values. Where only one has a node, the merged tree simply keeps that node.
So recurse on the two trees together, always looking at the same position in both.
x = a.val if a else 0 y = b.val if b else 0 total = x + y
- merged
- 6
The roots 2 and 4 are both present. The merged root is 6.
Reuse a whole subtree
When one side is empty, you do not need to copy the other side. Return it as it is, and all the nodes below it come along.
When both are present, create the merged node, or reuse one of the two nodes, with the summed value. Its left child is the merge of the two left children, and its right child is the merge of the two right children.
a.val = x + y # merge into the first tree
At some position the first tree is empty, and the second has a subtree with 100 nodes. What does the merge do there?
- AReturns the second tree's subtree as it is, without visiting its nodes
- BCopies all 100 nodes one at a time
- CLeaves the position empty
Show the answer
Returns the second tree's subtree as it is, without visiting its nodes. Nothing needs to be added, so the whole subtree is the result.
Merge two binary trees
You are given the roots of two binary trees root1 and root2. Merge them into a new tree: if two nodes overlap, the merged node's value is the sum of their values; otherwise, the node that is not empty is used as the node of the merged tree. Return the merged tree's root. The merge must start from the roots of both trees.
root1 = [1, 3, 2, 5], root2 = [2, 1, 3, null, 4, null, 7] → [3, 4, 5, 5, 4, null, 7]
0 ≤ number of nodes in each tree ≤ 2,000 · -10,000 ≤ node.val ≤ 10,000