0617. Merge Two Binary Trees¶
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.
Note: The merging process must start from the root nodes of both trees.
Example 1:
Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]
Example 2:
Input: root1 = [1], root2 = [1,2]
Output: [2,2]
Constraints:
- The number of nodes in both trees is in the range
[0, 2000]. -104 <= Node.val <= 104
Analysis¶
This question can be solved using DFS. For each DFS call, we should check if
- root1 is null
- root2 is null
- root1 and root2 are not null
Also, depending on the requirement, if we can modify on the existing input, we can just modify any values already on the input trees. If not, we should create a new node everytime we traverse the tree.
- Time: O(n) number of node in the tree
- Space: O(n) for linkedlist case
Code¶
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
// this check will handle all the case when any of the node is null
if (!root1 || !root2)
return root1 ? root1 : root2;
// At this point, all two nodes are not null
root1 -> val += root2 -> val;// modify the existing tree
root1 -> left = mergeTrees(root1 -> left, root2 -> left);
root1 -> right = mergeTrees(root1 -> right, root2 -> right);
return root1;
/* create new node
TreeNode *newNode = new TreeNode(root1 -> val + root2 -> val);
newNode -> left = mergeTrees(root1 -> left, root2 -> left);
newNode -> right = mergeTrees(root1 -> right, root2 -> right);
return newNode;
*/
}
};