相关推荐
python coding with ChatGPT 打卡第12天| 二叉树：理论基础
python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历
python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历
python coding with ChatGPT 打卡第15天| 二叉树：翻转二叉树、对称二叉树
python coding with ChatGPT 打卡第16天| 二叉树：完全二叉树、平衡二叉树、二叉树的所有路径、左叶子之和
python coding with ChatGPT 打卡第17天| 二叉树：找树左下角的值、路径总和
python coding with ChatGPT 打卡第18天| 二叉树：从中序与后序遍历序列构造二叉树、最大二叉树

合并二叉树

Key Points

将直接在 root1 上就地合并 root2，以避免额外的空间复杂度

相关题目

617. 合并二叉树

视频讲解

一起操作两个二叉树

重点分析

方法一：
递归（修改root1）

class Solution:
    def mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        # 递归终止条件: 
        #  但凡有一个节点为空, 就立刻返回另外一个. 如果另外一个也为None就直接返回None. 
        if not root1: 
            return root2
        if not root2: 
            return root1
        # 上面的递归终止条件保证了代码执行到这里root1, root2都非空. 
        root1.val += root2.val # 中
        root1.left = self.mergeTrees(root1.left, root2.left) #左
        root1.right = self.mergeTrees(root1.right, root2.right) # 右
        
        return root1 # ⚠️ 注意: 本题我们重复使用了题目给出的节点而不是创建新节点. 节省时间, 空间. 

方法二：
递归（创建新节点）

def mergeTrees(root1, root2):
    if not root1:
        return root2
    if not root2:
        return root1
    root = TreeNode(root1.val + root2.val)
    root.left = mergeTrees(root1.left, root2.left)
    root.right = mergeTrees(root1.right, root2.right)
    return root

方法三：
迭代法（修改root1）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def mergeTrees(root1, root2):
    if not root1:
        return root2
    if not root2:
        return root1
    
    # 使用队列存储需要合并的节点对
    queue = [(root1, root2)]
    while queue:
        node1, node2 = queue.pop(0)
        
        # 如果两个节点都不为 None，则合并它们的值
        if node1 is not None and node2 is not None:
            node1.val += node2.val
            
            # 如果 node1 的左子节点为空，我们直接将 node2 的左子节点链接过来
            if not node1.left:
                node1.left = node2.left
            else:
                queue.append((node1.left, node2.left))
            
            # 对于右子节点执行相同的操作
            if not node1.right:
                node1.right = node2.right
            else:
                queue.append((node1.right, node2.right))
                
    return root1

方法四：
迭代法（新建节点）

def mergeTrees(root1, root2):
    if not root1 and not root2:
        return None
    elif not root1:
        return TreeNode(root2.val, root2.left, root2.right)
    elif not root2:
        return TreeNode(root1.val, root1.left, root1.right)
    else:
        # 创建一个新节点，值为两个节点值的和
        newNode = TreeNode(root1.val + root2.val)
        
        # 使用队列存储节点对，以并行遍历两棵树
        queue = [(root1, root2, newNode)]
        
        while queue:
            node1, node2, new_node = queue.pop(0)
            
            # 处理左子节点
            if node1.left or node2.left:
                if node1.left and node2.left:
                    new_node.left = TreeNode(node1.left.val + node2.left.val)
                    queue.append((node1.left, node2.left, new_node.left))
                elif node1.left:
                    new_node.left = TreeNode(node1.left.val, node1.left.left, node1.left.right)
                else:  # node2.left
                    new_node.left = TreeNode(node2.left.val, node2.left.left, node2.left.right)
            
            # 处理右子节点
            if node1.right or node2.right:
                if node1.right and node2.right:
                    new_node.right = TreeNode(node1.right.val + node2.right.val)
                    queue.append((node1.right, node2.right, new_node.right))
                elif node1.right:
                    new_node.right = TreeNode(node1.right.val, node1.right.left, node1.right.right)
                else:  # node2.right
                    new_node.right = TreeNode(node2.right.val, node2.right.left, node2.right.right)
                    
        return newNode