合并二叉树

怎样从“合并两棵二叉树对应结点相加。”推导出 二叉树 · 合并，并证明每次状态变化都不会漏掉答案？

中心结论：递归:都非空则新结点 val=sum,递归左右;一空则返回另一。

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

在本站主例中，合并两棵二叉树对应结点相加。

算法最终需要得到或观察：合并树。

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 t1/t2 指针对齐。
3. 3转移每一步按照 递归:都非空则新结点 val=sum,递归左右;一空则返回另一。
4. 4收尾读取 合并树。，并复核边界与复杂度。

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：t1/t2 指针对齐。

简单题。采用深搜的思路，分别从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。两个二叉树的对应节点可能存在以下三种情况： 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空； 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点； 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。 对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。用递归实现即可。

递归:都非空则新结点 val=sum,递归左右;一空则返回另一。

执行过程中持续维护：t1/t2 指针对齐。

正确性依赖以下不变量：对应位置同步合并。

面试时可以压缩为：递归 O(min(n,m))。

落到当前题，执行机制可以压缩为：递归:都非空则新结点 val=sum,递归左右;一空则返回另一。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入合并两棵二叉树对应结点相加。 因为：递归:都非空则新结点 val=sum,递归左右;一空则返回另一。
2. 2同步递归比较值和结构都要一致。 因为：一处不同即可 false。
3. 31 vs 2 不一致提前结束。 因为：结构或值不同。
4. 4同步递归比较值和结构都要一致。 因为：一处不同即可 false。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6收尾与复杂度合并树。 因为：时间 O(n) · 空间 O(1)。递归:都非空则新结点 val=sum,递归左右;一空则返回另一。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

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
}

func main() {
    // 1. 主例
    //    输入：mode="same-tree", values=[1,3,2,5], valuesB=[2,1,3,null,4,null,7]
    //    期望：合并树。
    //
    // 2. 失败 / 未命中
    //    检查：结构不同处取非空子树。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC100 相同；LC105 建树
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意合并两棵二叉树对应结点相加。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化递归:都非空则新结点 val=sum,递归左右;一空则返回另一。
4. 4证明对应位置同步合并。
5. 5复杂度时间 O(n)，空间 O(1)