合并二叉树 图解题解

合并规则到底是什么

给两棵二叉树 t1、t2，把它们按位置叠加成一棵树：某个位置两棵树都有节点，新值等于两值之和；只有一棵有节点，就原样采用那个节点连同它下面的整棵子树。结果树的形状是两棵树形状的并集。可以想象两张画着树的透明胶片叠在一起：重叠处数值相加，不重叠处露出谁就是谁。

为什么这道题天然适合同步递归

合并的定义本身就是递归的：合并两棵树，等于合并两个根，再分别合并两边的左子树、两边的右子树——子问题和原问题一模一样，只是规模更小。于是让两个指针 a、b 同步下行，每一步只处理一对对应位置的节点。相比先把两棵树各自遍历成序列再对齐相加，同步递归根本不用处理两树形状不一致的对齐难题：位置的对应关系由递归结构自动维护，a 的左孩子永远只和 b 的左孩子配对。

一边为空为什么可以整支搬走

递归的终止条件是这题的精髓：a 为空就直接返回 b，b 为空就直接返回 a。理由是一旦一边为空，它下面的所有位置也全是空，按规则这一整片区域的结果都等于另一棵树的原样——那就不必再逐个节点走进去确认，直接把整棵子树接上。这一步不只是写法上的简洁，它直接决定了复杂度：递归只深入两树都有节点的重叠区域，非重叠的部分一步接走、零成本。

原地复用还是新建节点

参考代码选择原地复用：把 b 的值累加进 a（a.val += b.val），左右孩子分别接上递归结果，最后返回 a，全程不新建节点，空间开销最小。如果场景要求不修改输入，也可以每步新建节点、值取两者之和，逻辑完全不变，多花一份结果树的空间。

最容易犯的错是把终止条件写成「一边为空就返回空」——这会把另一边还完好的整棵子树直接丢掉，合并出的树缺一大块。正确语义是「一边为空，答案就是另一边」。

复杂度为什么是 O(min(m,n))

真正的递归只发生在两树重叠的位置：设两棵树分别有 m、n 个节点，重叠位置至多 min(m,n) 个，每个位置做一次相加和两次递归调用，时间 O(min(m,n))。递归栈深等于重叠部分的高度，即 O(min(h1,h2))，最坏两棵树都退化成重合的链时为 O(n)。另一个细节：合并是逐位置的，值相加之后必须继续递归左右孩子，只把两个根相加、忘了往下走，孩子层的叠加根本没发生。

Java

class Solution {
    public TreeNode mergeTrees(TreeNode a, TreeNode b) {
        if (a == null) return b;            // 一边空 → 搬另一边整支
        if (b == null) return a;
        a.val += b.val;                      // 都非空 → 对应位置相加
        a.left  = mergeTrees(a.left,  b.left);   // 递归合并左
        a.right = mergeTrees(a.right, b.right);  // 递归合并右
        return a;
    }
}

Python

class Solution:
    def mergeTrees(self, a: TreeNode, b: TreeNode) -> TreeNode:
        if a is None: return b              # 一边空 → 搬另一边整支
        if b is None: return a
        a.val += b.val                       # 都非空 → 对应位置相加
        a.left  = self.mergeTrees(a.left,  b.left)   # 递归合并左
        a.right = self.mergeTrees(a.right, b.right)  # 递归合并右
        return a

C++

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* a, TreeNode* b) {
        if (a == nullptr) return b;          // 一边空 → 搬另一边整支
        if (b == nullptr) return a;
        a->val += b->val;                     // 都非空 → 对应位置相加
        a->left  = mergeTrees(a->left,  b->left);   // 递归合并左
        a->right = mergeTrees(a->right, b->right);  // 递归合并右
        return a;
    }
};