465. Overlay Two Trees
Two transparent blueprints of a building are drawn as binary trees, a and b. When the blueprints are laid on top of each other, nodes that sit at the same position (the same sequence of left and right moves from the root) are fused into one node whose value is the sum of the two values. At a position where only one blueprint has a node, that node is used as it is, together with everything below it.
Return the root of the overlaid tree. If both inputs are empty the result is empty, and if only one is empty the result is a copy of the other. The returned tree is compared by shape and values.
Example 1
- Input:
- a = [2,1,3,5], b = [4,null,6,null,7]
- Output:
- [6,1,9,5,null,null,7]
- Explanation:
Roots add to 6; the left child 1 (with child 5) has no partner so it is kept, the right children add to 9, and 7 has no partner so it is kept.
Example 2
- Input:
- a = [], b = [3,-1,2]
- Output:
- [3,-1,2]
- Explanation:
One tree is empty, so the result is a copy of the other.
Constraints
0 ≤ number of nodes in each of a and b ≤ 1000
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(min(n, m))
- Space
- O(min(h1, h2))