相同的树

怎样从“比较树 p=[1,2,3] 与 q=[1,2,3] 是否相同。”推导出 二叉树 · 相同，并证明每次状态变化都不会漏掉答案？

中心结论：同步递归:根相等则递归比左右;任一 null 不等则 false。

这一题要求判断 2 颗树是否是完全相等的。

在本站主例中，比较树 p=[1,2,3] 与 q=[1,2,3] 是否相同。

算法最终需要得到或观察：结构值全同,返回 true。

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

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

1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
2. 2状态只维护 p/q 指针对齐、相等性。
3. 3转移每一步按照 同步递归:根相等则递归比左右;任一 null 不等则 false。
4. 4收尾读取 结构值全同,返回 true。，并复核边界与复杂度。

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

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

同步递归:根相等则递归比左右;任一 null 不等则 false。

执行过程中持续维护：p/q 指针对齐、相等性。

正确性依赖以下不变量：对应子树同步比较,结构必须一致。

面试时可以压缩为：isSameTree(p,q): p/q 同空 true;一空 false;值不等 false;否则递归左右。时间 O(n),空间 O(h) 最坏 O(n)。

落到当前题，执行机制可以压缩为：同步递归:根相等则递归比左右;任一 null 不等则 false。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入比较树 p=[1,2,3] 与 q=[1,2,3] 是否相同。 因为：同步递归:根相等则递归比左右;任一 null 不等则 false。
2. 2同步递归比较值和结构都要一致。 因为：一处不同即可 false。
3. 3结点 1 相同,递归子树继续比左右。 因为：同构需递归成立。
4. 4结点 2 相同,递归子树继续比左右。 因为：同构需递归成立。
5. 5预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
6. 6结点 3 相同,递归子树继续比左右。 因为：同构需递归成立。
7. 7两树相同递归完成。 因为：O(n) 同步遍历。
8. 8收尾与复杂度结构值全同,返回 true。 因为：时间 O(n) · 空间 O(h)。同步递归:根相等则递归比左右;任一 null 不等则 false。

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

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

func isSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	} else if p != nil && q != nil {
		if p.Val != q.Val {
			return false
		}
		return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
	} else {
		return false
	}
}

func main() {
    // 1. 主例
    //    输入：mode="same-tree", values=[1,2,3], valuesB=[1,2,3]
    //    期望：结构值全同,返回 true。
    //
    // 2. 失败 / 未命中
    //    检查：只比值不比结构会错。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC101 对称；LC104 深度
}

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

1. 1题意比较树 p=[1,2,3] 与 q=[1,2,3] 是否相同。
2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
3. 3优化同步递归:根相等则递归比左右;任一 null 不等则 false。
4. 4证明对应子树同步比较,结构必须一致。
5. 5复杂度时间 O(n)，空间 O(h)