Problem Description
You are given two binary trees root1 and root2. Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree. Return the merged tree. The merging process must start from the root nodes of both trees.
Key Insights
- The merge operation is recursive, processing nodes from the top (root) to the bottom (leaves).
- For each pair of nodes, if both are present, their values are summed.
- If only one node is present, that node is used in the merged tree.
- The process involves traversing both trees simultaneously.
Space and Time Complexity
Time Complexity: O(n), where n is the number of nodes in the merged tree since we need to visit each node once.
Space Complexity: O(h), where h is the height of the tree, due to the recursive call stack.
Solution
The solution uses a recursive depth-first search approach to traverse both binary trees simultaneously. At each step, we check if both nodes exist. If they do, we create a new node with the sum of their values. If only one of the nodes exists, we use that node. The algorithm builds the merged tree in a bottom-up manner until all nodes are processed.