LC100 相同的树 · 逐题动画 · RuntimeScope

RuntimeScope/算法实验台/56 天打卡/141 题/LC100

题型地图 56天全屏 141题

当前：LC100 · 相同的树 · 首次出现于 Day 16 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC98 LC101 →

39 / 141回到 Day 16 卡片 141 题索引

LC100 · 相同的树 · 工程执行实验室

双树双人安检

两个指针 p 和 q 永远站在两棵树的同一位置，同步递归比较。讲清楚 base case、值否决、左右子树拆分，以及 false 如何沿调用栈向上传递。

p = [1, 2, 3]

q = [1, 2, 3] 或 [1, 2, 4]

核心 · 双树同步比较

isSameTree(p, q) 判断的不是两个节点是否一样，而是以 p 和 q 为根的两棵子树是否完全一样。

· 两个指针 p、q 永远站在对应位置。
· 结构相同 + 对应值相同，两棵子树才相同。
· 当前层通过后，继续递归左子树和右子树。

双人安检 · 同步递归

两个指针 p 和 q 像两列安检员，永远站在两棵树的同一相对位置。当前层检查通过后，再分别进入左、右子树继续安检。

both nil → true
one nil → false
value diff → false
recurse left && right

递归调用栈：进入压栈，返回弹栈

1.每次 isSameTree(p, q) 调用都会在系统栈上保存一帧暂停状态。
2.子问题返回 true/false 后弹栈，结果用 && 合并给上一层。
3.一处 false 会沿栈向上传递，最终根调用也返回 false。

1/9 · 题目区

9 步分镜：

Step 1题目区

题目目标：相同的树 = 结构相同 + 对应值相同

给定两棵二叉树 p 和 q，判断它们是否完全相同。不仅要根节点值一样，左右子树的形状和对应位置的值也必须一一对应。

为什么

「相同」是整棵子树级别的命题：结构对齐且每个对应节点值相等。

状态表 · p / q / 调用栈

p	q	调用栈（底 → 顶）	返回值	动作
p → 1（p-0）	q → 1（q-0）	[]	—	读题p=[1,2,3]，q=[1,2,3]

p 左 · q 右·高亮 = 当前比较对·中线 = 对应位置

递归栈 · 当前调用链

（空栈）

Go · isSameTree

1func isSameTree(p *TreeNode, q *TreeNode) bool {
2    if p == nil && q == nil {
3        return true
4    }
5    if p == nil || q == nil {
6        return false
7    }
8    if p.Val != q.Val {
9        return false
10    }
11    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
12}

复杂度

时间: O(n)
空间: O(h)

每个节点最多被比较一次，n 为两树节点总数。

h 为树高。平衡树约 O(log n)，最坏退化链表为 O(n)。递归版用系统调用栈保存暂停状态。

面试回答

两棵二叉树相同，当且仅当结构相同且对应位置值相同。递归函数 isSameTree(p,q)：p 和 q 都空返回 true；一空一非空返回 false；值不等返回 false；否则 return isSameTree(p.Left,q.Left) && isSameTree(p.Right,q.Right)。时间 O(n)，空间 O(h)，最坏 O(n)。

常见误区

误区 1：只比根节点值

根相等不够，必须递归比较整棵左子树和整棵右子树。

误区 2：忽略结构

一边有子节点、另一边为空，即使已有节点值相同也返回 false。

误区 3：空间复杂度写成 O(1)

递归实现需要调用栈，空间是 O(h)，最坏退化链表时 O(n)。

误区 4：把「节点相同」当成「子树相同」

isSameTree(p, q) 判断的不是两个节点是否一样，而是以 p 和 q 为根的两棵子树是否完全一样。