合并二叉树

合并二叉树_牛客题霸_牛客网

问题简述

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。

思路

• 前序遍历，定义 dfs(x1, x2)：

  • 如果 x1 和 x2 都非空， t1.val += t2.val；

  • 对左子树：

    • 如果 x1.left 和 x2.left 都非空，则 dfs(x1.left, x2.left)；

    • 如果 x1.left 为空，x1.left = x2.left；

    • x2.left 为空的情况，可以跳过；

  • 右子树同理；

Python 写法1

class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        if not t1: return t2
        
        def dfs(x1, x2):
            if not x1 or not x2: return
            
            x1.val += x2.val
            # 左子树
            if x1.left and x2.left: 
                dfs(x1.left, x2.left)
            elif not x1.left: 
                x1.left = x2.left
            # 右子树
            if x1.right and x2.right: 
                dfs(x1.right, x2.right)
            elif not x1.right: 
                x1.right = x2.right
        
        dfs(t1, t2)
        return t1

Python 写法2（更优雅）

class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        
        def dfs(x1, x2):
            if not x1 or not x2: return x1 or x2
            x1.val += x2.val
            x1.left = dfs(x1.left, x2.left)
            x1.right = dfs(x1.right, x2.right)
            return x1
        
        return dfs(t1, t2)