Merge Two Binary Tree

Link Merge Two Binary Trees

Problem #

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.

Thoughts #

We just need to traverse both trees and return the merge TreeNode to parent node.

Solution #

# 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]:
        def dfs(root1,root2):
            if not root1 and not root2:
                return 
            val=0
            l1,r1,l2,r2=None,None,None,None
            if root1:
                val+=root1.val
                l1=root1.left
                r1=root1.right
            if root2:
                val+=root2.val
                l2=root2.left
                r2=root2.right
            l=dfs(l1,l2)
            r=dfs(r1,r2)
            return TreeNode(val,l,r)
        return dfs(root1,root2)

Explanation #

• We use a simple dfs to go over all tree nodes.
• We use l1,r1,l2,r2 to store the left and right child of root1 and root2 respectively. We assign value instead of directly use root1 and root2 sometimes root1 or root2 may be None and we can’t get the child of None.

Insights #

• Return new nodes will make it easier to handle undecided tree structure.