Merged binary tree of leetcode

subject

Here are two binary trees ： root1 and root2 .

Imagine , When you cover one tree over the other , Some nodes on the two trees will overlap （ And others don't ）. You need to merge these two trees into a new binary tree . The rule of consolidation is ： If two nodes overlap , Then add the values of the two nodes as the new values of the merged nodes ; otherwise , Not for null The node of will be the node of the new binary tree directly .

Returns the merged binary tree .

Be careful : The merge process must start at the root 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]
 

Tips ：

The number of nodes in the two trees is in the range [0, 2000] Inside
-104 <= Node.val <= 104

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/merge-two-binary-trees
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas

#  Merge the corresponding positions of the binary tree 
'''
 Three situations :
    1. Both the left subtree and the right subtree have values , Then add them 
    2. Left （ Right ） Subtree has value , Right （ Left ） Subtree has no value , Only the left subtree is added 
    3. The left subtree has no value , Right subtree has no value , Do not add 

 Traversing to any node is like this , So you can use recursion , After traversing the current node , Sure 
 Then recursively traverse the left and right subtrees of the current node respectively 
'''

Source 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: TreeNode, root2: TreeNode) -> TreeNode:

        #  As long as a subtree traversal is completed , Then all the rest of the other subtree will return 
        if not root1: return root2
        if not root2: 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

Through screenshots

  Synchronous update in personal blog system ：LeetCode Merge binary tree