合并二叉树 - Stellar Observer Protocol

617 字

3 分钟

合并二叉树

2025-08-10

Algorithms

树

/

深度优先搜索

/

广度优先搜索

/

二叉树

题目描述#

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

解题思路#

递归合并策略：
- 若两树当前节点均非空，创建新节点（值 = t1.val + t2.val）
- 递归合并左子树（t1.left 与 t2.left）
- 递归合并右子树（t1.right 与 t2.right）
单树处理：
- 若仅一棵树节点非空，直接返回该节点（子树自动接入）
- 若两节点均空，返回 null
原地优化：
- 可在树 t1 上直接修改，避免新建节点（需题目允许）

关键洞察#

递归终止条件：
- 任一树节点为空时，直接返回另一树的节点（包含子树）
- 双空节点返回 null，自然终止递归
子树自动继承：
- 当仅一侧树存在子树时，新树直接继承该子树（无需额外操作）
无重叠覆盖：
- 因二叉树结构固定，合并只需处理重叠节点值的相加
时空平衡：
- 递归深度由较深树决定，每节点仅访问一次

复杂度分析#

指标	说明
时间复杂度	O(min(m,n))：m/n 为两树节点数，递归遍历重叠区域（非重叠节点直接返回）
空间复杂度	O(min(m,n))：递归栈深度由较浅树高度决定，最坏情况 O(min(m,n))

代码实现#

非原地修改

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root1
11
 * @param {TreeNode} root2
12
 * @return {TreeNode}
13
 */
14
var mergeTrees = function (root1, root2) {
15
    if (!root1) return root2;
16
    if (!root2) return root1;
17
    const root = new TreeNode()
18
    root.val = root1.val + root2.val
19
    root.left = mergeTrees(root1.left, root2.left)
20
    root.right = mergeTrees(root1.right, root2.right)
21
    return root
22
};

原地修改

1
/**
2
 * Definition for a binary tree node.
3
 * function TreeNode(val, left, right) {
4
 *     this.val = (val===undefined ? 0 : val)
5
 *     this.left = (left===undefined ? null : left)
6
 *     this.right = (right===undefined ? null : right)
7
 * }
8
 */
9
/**
10
 * @param {TreeNode} root1
11
 * @param {TreeNode} root2
12
 * @return {TreeNode}
13
 */
14
const mergeTrees = (t1, t2) => {
15
    if (!t1) return t2;
16
    if (!t2) return t1;
17
    t1.val += t2.val;
18
    t1.left = mergeTrees(t1.left, t2.left);
19
    t1.right = mergeTrees(t1.right, t2.right);
20
    return t1;
21
};