第5章｜二叉树与递归
Unit 03 · LeetCode #101 对称二叉树
对称不是“左右一样”，
而是两棵子树按镜像位置成对相等。
Unit 02 主动交换左右引用来制造镜像；本单元不再修改树，而是让递归函数同时接收两个节点，持续检查“外侧对外侧、内侧对内侧”的镜像配对关系。
已恢复上次学习位置阶段、动画、槽位、代码和迁移进度已恢复。
知识桥梁｜Unit 02 → Unit 03
Unit 02：制造镜像
invertTree(root) 接收一个节点，递归处理两棵子树，再交叉改写 left/right 引用。
修改结构 → 验证关系
Unit 03：比较镜像
isMirror(left, right) 同时接收两个节点，不改引用，只判断当前值和两组交叉子问题。
本单元贯穿问题当前比较的是哪一对节点？下一层应生成“同向配对”还是“交叉配对”？
LeetCode #101 原题题面转述、示例与函数签名
题目要求
给定一棵二叉树的根节点 root，检查它是否轴对称。轴对称要求根的左右子树互为镜像。
class Solution:
def isSymmetric(
self,
root: Optional[TreeNode]
) -> bool:
pass
约束
- 节点数范围为
[1, 1000]； -100 ≤ Node.val ≤ 100。
示例
输入：root = [1,2,2,3,4,4,3]
输出：true
输出：true
输入：root = [1,2,2,null,3,null,3]
输出：false
输出：false
主方法
递归比较镜像节点对。每个节点进入一次比较，时间复杂度 O(n)；递归栈为 O(h)。
镜像节点对
它们不一定处于相同方向，而是关于根的竖直轴位置互换。
双节点契约
函数一次接收两个子树根，返回这两棵子树是否互为镜像。
外侧配对
left.left 必须与 right.right 继续比较。
内侧配对
left.right 必须与 right.left 继续比较。
镜像树观察当前橙色镜像配对线
蓝色：比较参数 left紫色：比较参数 right虚线：当前镜像配对
待处理／已处理的节点对
当前函数契约isMirror(left, right) 返回两棵子树是否互为镜像
调用栈（顶部为当前比较）
尚未进入递归轨迹
leftnode 2
rightnode 2
当前判断值相等
下一组配对外侧 + 内侧
当前结论尚未完成全部节点对
根据当前动画状态回答
先观察树上高亮的两个节点及配对线。
补全 #101 提交代码把双节点契约编译成 8 个槽位
class Solution:
def isSymmetric(self, root):
def isMirror(left, right):
if :
return
if :
return
if :
return False
return (
and
)
return
代码—节点对—调用栈联动1 / 1
left / right—
结构判断—
值判断—
新建子问题—
返回结果—
进入 isSymmetric。
完成槽位或播放完整轨迹后进入迁移迁移 #100 只改变配对方向，不从空白代码开始。
迁移目标：LeetCode #100 相同的树
复用“双节点递归比较”的骨架，但镜像问题的交叉配对改为同向配对。先比较变化，再拼槽位，最后用非相同树的轨迹验证。
LeetCode #100｜相同的树｜Same Tree
标签：树 · 深度优先搜索 · 广度优先搜索
迁移原题
给定两棵二叉树的根节点 p 和 q，判断它们是否相同。两棵树相同，当且仅当结构相同且对应节点值相同。
class Solution:
def isSameTree(
self,
p: Optional[TreeNode],
q: Optional[TreeNode]
) -> bool:
pass
示例
输入：p = [1,2,3], q = [1,2,3]
输出：true
输出：true
输入：p = [1,2], q = [1,null,2]
输出：false
输出：false
输入：p = [1,2,1], q = [1,1,2]
输出：false
输出：false
复用“双节点契约”，不复用交叉方向
#101 已掌握
同时处理两个节点：双空为真、单空为假、值不同为假，再递归比较两对子树。
保留骨架
替换方向
替换方向
#100 新任务
对应位置必须一致，所以比较 p.left ↔ q.left 与 p.right ↔ q.right。
当前任务是“对应位置相同”，根节点相等后第一组子问题应是什么？
观察“对应位置”意味着左右方向不交换。
镜像比较与相同树比较只差一个关键维度
| 维度 | #101 对称二叉树 | #100 相同的树 |
|---|---|---|
| 参数 | left, right | p, q |
| 结构边界 | 双空真、单空假 | 双空真、单空假 |
| 当前值 | left.val == right.val | p.val == q.val |
| 第一组子问题 | left.left ↔ right.right | p.left ↔ q.left |
| 第二组子问题 | left.right ↔ right.left | p.right ↔ q.right |
若当前动画比较 p.left=node2 与 q.left=None，应立即返回什么？
这一问只依赖“当前这一对”的结构状态。
选择代码片段，再点击对应槽位
片段库
isSameTree 骨架
用结构不一致案例验证同向配对
当前 p / q1 / 1
当前结构都存在
当前值1 == 1
返回／生成生成同向子问题
案例：p=[1,2]，q=[1,null,2]。根节点相等，下一步必须比较左对左。
Unit 03 Skill 卡
对称判断的关键不是遍历顺序，而是把树转写为一系列“镜像节点对”。递归函数每次只审查一对节点，并生成外侧与内侧两个交叉子问题；迁移到相同树时，边界与值判断不变，只把交叉配对改为同向配对。
核心契约isMirror(left,right) 判断两棵子树是否镜像
结构边界双空为真，单空为假
当前节点两个值必须相等
镜像递归外侧对外侧，内侧对内侧
复杂度时间 O(n)，递归栈 O(h)
迁移信号双节点递归；改变配对方向即可迁移
本环节已完成
请停留观察当前状态，确认你能解释高亮节点对为什么成立或失败。
环节 1 / 6