Merging Binary Trees

Given two binary trees node0 and node1, return a merge of the two trees where each value is equal to the sum of the values of the corresponding nodes of the input trees. If only one input tree has a node in a given position, the corresponding node in the new tree should match that input node.

Constraints

• n ≤ 100,000 where n is the number of nodes in node0
• m ≤ 100,000 where m is the number of nodes in node1

https://binarysearch.com/problems/Merging-Binary-Trees

Examples

Example 1

Input

• node0 =

• node1 =

Output

• answer =

Example 2

Input

• node0 =

• node1 =

Output

• answer =

Solution