vvrf / DSA.log

问题拆解

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

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

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

同步递归

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;
}

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

func mergeTrees(a, b *TreeNode) *TreeNode {
    if a == nil {
        return b
    }
    if b == nil {
        return a
    }
    a.Val += b.Val
    a.Left = mergeTrees(a.Left, b.Left)
    a.Right = mergeTrees(a.Right, b.Right)
    return a
}

pub fn merge_trees(
    a: Option<Rc<RefCell<TreeNode>>>,
    b: Option<Rc<RefCell<TreeNode>>>,
) -> Option<Rc<RefCell<TreeNode>>> {
    match (a, b) {
        (None, rest) | (rest, None) => rest,
        (Some(a), Some(b)) => {
            {
                let mut an = a.borrow_mut();
                let bn = b.borrow();
                an.val += bn.val;
                an.left = Self::merge_trees(an.left.take(), bn.left.clone());
                an.right = Self::merge_trees(an.right.take(), bn.right.clone());
            }
            Some(a)
        }
    }
}

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

复杂度

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

可以迁移的模式

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

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