LeetCode 617. 合并二叉树

约 4 分钟
文章信息 15 个分类 4 个标签
分类
LeetCode CodeTop 简单 已解决 10-20 字节 阿里 微软 美团 拼多多 小米 百度 网易 快手 携程
标签
深度优先搜索 树 广度优先搜索 二叉树

题目描述

✅ 617. 合并二叉树

image-20260928221312865

image-20260928221312866

题意分析

从两棵二叉树的根开始，按照相同的左右路径对齐节点。对应位置都有节点时，把两个值相加；只有一棵树有节点时，保留这一侧的节点及其子树；两侧都为空时，结果也为空。

返回合并后树的根节点。这里的“对应”指结构位置相同，而不是节点值相同或在各自遍历中排名相同。题目允许复用原节点，无须为结果复制一整棵独立的新树。

解法：递归原地合并

核心思路

[!blue]

定义 mergeTrees(root1, root2) 返回这两个位置所代表子树的合并结果。递归中的两个参数始终处于各自原树的同一结构位置，左孩子只与左孩子合并，右孩子只与右孩子合并。

若 root1 为空，当前位置及其后续只可能由第二棵树提供，直接返回 root2；反之返回 root1。这不只是空指针边界，也表示无需继续遍历这棵单独存在的子树，它本身就是正确结果。两侧都为空也由上述分支自然处理。

两侧都存在时，复用 root1 作为结果节点，把 root2 的值加到它上面。然后分别递归合并左右孩子，并把递归返回值接回 root1.left、root1.right。仅调用递归而不接收返回值是不够的：当第一棵树缺少某个孩子时，需要靠返回值把第二棵树独有的子树挂上来。

左右递归都完成后，当前节点的值和两棵结果子树就都符合合并规则，返回 root1 供上一层继续连接。整个过程只向同时存在的节点对深入，不处理无需合并的单侧区域。

该实现会修改第一棵树重叠位置的节点值和孩子连接，并可能直接挂入第二棵树的子树。因此结果会复用输入节点，附接部分与第二棵树共享引用；它不保证结果是一份与输入完全独立的副本。

解题步骤

  1. 第一侧为空时返回第二侧；第二侧为空时返回第一侧。
  2. 两侧都存在时，执行 root1.val += root2.val。
  3. 将两个左孩子的递归合并结果赋给 root1.left。
  4. 将两个右孩子的递归合并结果赋给 root1.right。
  5. 返回当前复用的 root1。

代码实现

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(r + 1)$，其中 r 为两个位置都存在节点的重叠节点对数量。每个重叠节点只继续调用左右两次，遇到单侧为空即常量时间返回，不会遍历整棵非重叠子树。
  • 空间复杂度：$O(h + 1)$，其中 h 为重叠区域沿根向下的最大深度。空间来自递归栈，不额外创建结果节点；若两树节点数为 m、n，最坏为 $O(\min(m, n) + 1)$。

关键点总结

[!green]

  • 合并按结构位置同步递归，单侧为空时直接采用另一棵子树。
  • 递归返回的是该位置的新子树入口，父节点必须接住返回值。
  • 复用节点避免复制非重叠区域，同时也意味着结果和输入可能共享子树。

易错点总结

[!yellow]

  • 只在两侧都为空时返回，会在仅一侧为空时仍访问空节点的值或孩子。
  • 一侧为空却返回空，会丢掉另一侧本应保留的整棵子树。
  • 只递归调用、不赋值给当前孩子，无法连接第一棵树原本缺失的那一侧。
  • 把不同方向的孩子配对，会改变题目按同一结构位置合并的含义。
  • 将返回树当成深拷贝继续修改，可能同时改变其复用的输入节点，应明确当前方法的共享关系。

相似题目

题目 难度 关联与区别
100. 相同的树 简单 同样同步遍历两棵树，本题在节点都存在时合并值，并处理只有一侧存在的子树。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/38409747
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！