合并二叉树

问题拆解

把两棵树叠在一起：重叠处的值相加，只有一棵有节点的地方就保留那个节点。要点在于两棵树的形状不一定相同，某个位置可能一边有、一边没有。

如果先分类讨论「四种组合」会很乱，不如让两个指针 a、b 从两棵树的根开始同步往下走，在每一层只问一个问题：这两个位置分别是否有节点。

一旦某一边为空，剩下的整棵子树就原封不动地属于另一边，根本不必再往下递归。

同步递归

def mergeTrees(a, b):
    if not a:
        return b
    if not b:
        return a
    a.val += b.val
    a.left = mergeTrees(a.left, b.left)
    a.right = mergeTrees(a.right, b.right)
    return a

前两行是全部的「让位」逻辑：只要有一边空，直接返回另一边——它可能是一整棵子树，也可能是 None，都正确。走到第三行时两边必然都存在，才需要相加并继续对齐左右孩子。这里选择把结果就地写回 a，省去新建节点；若不想改动入参，把 a.val += b.val 换成新建节点即可。

复杂度

指标	复杂度	原因
时间	O(min(m, n))	只在两树重叠的部分才继续递归
空间	O(min(h1, h2))	递归深度取决于较早触底的那棵树

可以迁移的模式

• 同时处理多棵树时，让所有指针「步调一致」地下探，能把情况数压到最少；
• 把「某一边缺失」设计成直接返回另一边，就能优雅地跳过整片子结构；
• 先写边界返回、再写「都存在」的主逻辑，思路会比穷举组合清晰得多。

「谁空了就交给对方」这种让位式收口，在合并、叠加类问题里反复出现。