LeetCode 617. 合并二叉树

2025-10-29 HGNULB 约 4 分钟

文章信息 12 个分类 5 个标签

分类

LeetCode CodeTop 简单已解决 10-20 字节跳动微软美团阿里巴巴快手拼多多网易

题目描述

✅ 617. 合并二叉树

题意分析

题目给两棵二叉树，要求把它们「叠」在一起：把两棵树的根对齐，然后同一位置上的节点如果都存在，就把值相加；如果只有一侧存在，就直接用那一侧的节点；两侧都不存在，那个位置就是空。返回合并后那棵树的根。

这里有一个最容易读漏的信号：只有一侧存在时，保留的是那一整棵子树，而不只是那一个节点。也就是说一旦另一侧已经走到空，剩下的部分不需要再逐个节点处理，整块搬过来即可。这一点既决定了正确性，也决定了复杂度。

另一个信号是题目允许返回其中一棵输入树作为结果，没有要求「不得修改输入」。这给了就地复用节点的空间；但如果面试官额外补一句「输入不能被改动」，写法就要换成新建节点，这个区别值得在写之前先跟面试官确认。

边界情况有三类：两棵树都为空，答案为空；一棵为空另一棵非空，答案就是非空的那棵；两棵形状完全不同，重叠区域可能只有根一个节点。这三种都应该被同一套逻辑自然覆盖。

解法：递归原地合并

核心思路

二叉树的左右子树天然具有相同结构，适合递归。先约定递归契约：mergeTrees(a, b) 返回两棵子树合并后的根。

a 为空，直接返回 b；b 为空，直接返回 a。这不是只保留一个节点，而是复用非空侧的整棵子树。

两者都非空时，把值累加到 a，再分别合并左右子树。

本解法会修改第一棵树，换来不创建新节点。若题目要求输入不可变，应在重叠位置创建新节点，并递归复制其左右子树。

递归不变量：每次调用返回时，以返回节点为根的整棵子树已经合并完毕。因此左右递归的返回值必须重新赋给 a.left 和 a.right。

解题步骤

任一根节点为空，返回另一侧子树，作为递归出口。

两个根都存在时，执行 root1.val += root2.val。

递归合并左右孩子，并接住两个返回值。

返回复用后的 root1。

例如 root1 = [1,3,2,5]、root2 = [2,1,3,null,4,null,7]：根节点得到 3；左子树根得到 4，独有的节点 5 和 4 被直接保留；右子树根得到 5，并接上独有节点 7，结果为 [3,4,5,5,4,null,7]。

代码实现

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }

        // 复用 root1 节点作为合并后的节点。
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
    if root1 == nil {
        return root2
    }
    if root2 == nil {
        return root1
    }

    // 两个节点都存在时，值相加并继续合并子树。
    root1.Val += root2.Val
    root1.Left = mergeTrees(root1.Left, root2.Left)
    root1.Right = mergeTrees(root1.Right, root2.Right)
    return root1
}

复杂度分析

时间复杂度：$O(k)$，其中 $k$ 是两棵树形状重叠的节点数；遇到任一空子树便停止深入，因此 $k \leq \min(m,n)$。

空间复杂度：$O(h)$，其中 $h$ 是重叠区域的最大递归深度；最坏为 $O(\min(m,n))$。结果复用原节点，不计入额外空间。

关键点总结

面试先说清递归契约：返回的是当前两棵子树的完整合并结果。

一侧为空时整棵返回，既是递归出口，也避免遍历非重叠区域。

左右递归结果必须接回父节点，否则无法挂上另一棵树独有的子树。

原地解法会修改 root1；不可修改输入时才改为新建节点。

易错点总结

只在“两者都为空”时返回，会在一侧为空时解引用空指针；两个单边为空的出口都要有。

一侧为空却返回 null，会丢掉另一侧的整棵子树。

只递归而不赋值，如 mergeTrees(root1.left, root2.left)，无法把另一侧独有的孩子挂回来。

未确认能否修改输入就原地复用 root1，可能违反题目的深拷贝或不可变约束。

相似题目

题目	难度	考察点
100. 相同的树	简单	两棵树同步遍历并逐位比较
101. 对称二叉树	简单	镜像位置成对递归
226. 翻转二叉树	简单	递归就地改写子树指针
572. 另一棵树的子树	简单	在大树上枚举起点做子树匹配
951. 翻转等价二叉树	中等	允许交换左右孩子的同构判定
剑指 Offer 26. 树的子结构	中等	子结构包含关系，可不到叶子