Two maps of the same region are drawn as binary trees; a node's value is the number of sightings recorded at that spot. Overlay the two maps: wherever both trees have a node the values are added, and wherever only one tree has a node that node is kept as it is. Return the root of the combined tree.
Examples
1 2 3
/ \ / \ / \
3 2 + 1 3 = 4 5
/ \ \ / \ \
5 4 7 5 4 7
Input: a = build_tree([1, 3, 2, 5]), b = build_tree([2, 1, 3, None, 4, None, 7])
Output: tree_to_list(...) == [3, 4, 5, 5, 4, None, 7]
Input: a = build_tree([1]), b = build_tree([])
Output: [1]
Constraints
0 <= number of nodes in each tree <= 1000-1000 <= node.val <= 1000
Goals
- Recurse over two trees in lockstep
- Handle the case where only one of the two nodes exists