617 Merge Two Binary Trees

1. 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 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.

 

constraints :

• The number of nodes in both trees is in the range [0, 2000].
• \(-10^{4}\) <= Node.val <= \(10^{4}\)

 

2. Algorithms

To merge two binary tree, we will make new node for merged tree while we traversing two trees. When we traverse two trees, we can meet few cases such as below : 

1. Both two nodes have values.
2. One node has value, but the other doesn't.
3. Both two nodes doesn't have values.

When we meet first case, we just make new node with value (root1.val + root2.val) and add node to merged tree. In case 2, we just add node with value to merged tree. In case 3, we add None to merged tree.

 

1. Start
2. If root1 is None and root2 is None, return None
3. If root1 is None and root2 is not None, return root2.
4. If root2 is None and root1 is not None, return root1.
5. Calculate new node of merged tree and store result into root.
6. Update left chlid of root node recursively using left childs of root1 and root2.
7. Update right child of root node recursively using right childs of root1 and root2.
8. Return the root.
9. End

 

To make more faster code, we will update merged on root1 while traversing two trees.

1. Start
2. If root1 is None, return root2.
3. If root2 is None, return root1.(In this case, we don't have to consider both two nodes don't have values.)
4. Update value of root1 incremented by value of root2.
5. Update root1.left with recursive result of left childs.
6. Update root.right wiht recursive result of right childs.
7. End

 

3. Codes

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 is None and root2 is None : 
            return None 
        if root1 is None and root2 is not None : 
            return root2
        if root1 is not None and root2 is None :
            return root1 
        
        root = TreeNode(root1.val + root2.val) 
        root.left = self.mergeTrees(root1.left, root2.left)
        root.right = self.mergeTrees(root1.right, root2.right)
        return root 
        
        
# Faster code
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 is None : 
            return root2
        if root2 is None :
            return root1 
        
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

 

4. Conclusion