第5章｜二叉树与递归
Unit 02 · LeetCode #226
← Unit 01
226
Invert Binary TreeReference · DFS · Transfer
先看见“引用重连”，
再把它编译成递归代码。
本单元沿用六段主流程。动画只保留静态文字无法替代的信息：父调用暂停、两棵子树返回、赋值过程中的瞬时引用状态，以及镜像比较时真正被配对的两个位置。
Unit 00 / Unit 01 概念桥先统一后续会反复使用的术语；本题重点从“返回数值”升级到“修改引用并返回子树根”。
节点与引用节点保存 val、left、right；树结构由引用而非数值决定。
子树根一个引用指向子树根，也就间接连接整棵后代结构。
原地修改不新建整棵树，直接更新已有节点的 left/right。
函数契约invertTree(root) 返回已经翻转完成的当前子树根。
后序语义先取得两个子树结果，再在当前节点完成交叉重连。
调用栈父函数暂停，保存局部状态，等待子调用返回后恢复。
引用覆盖覆盖前必须保存原引用，否则第二次赋值可能读到已变化状态。
return root让父调用获得已处理子树根，用于继续向上重连。
镜像关系外侧与外侧配对，内侧与内侧配对，而非同方向比较。
复杂度 n / h每节点常数次修改，总时间 O(n)，递归栈 O(h)。
LeetCode #226 原题信息题面转述 · 示例 · 复杂度目标
题目要求
给定二叉树根节点 root，翻转这棵树并返回根节点。翻转意味着：对树中每个节点交换其左子树与右子树。
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
pass
约束
- 节点数量范围为
[0, 100]； -100 ≤ Node.val ≤ 100。
示例
输入：[4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
输入：[2,1,3]
输出：[2,3,1]
输入：[]
输出：[]
目标方法
递归 DFS 原地修改引用：时间 O(n)，调用栈空间 O(h)。
六段主流程
官方示例树当前动画状态
蓝线：left紫线：right绿线：刚完成重连虚线：当前镜像比较对
当前函数契约invertTree(root) → 已翻转的当前子树根
当前真实引用
调用栈（顶部为当前函数）
当前环节尚未进入代码轨迹
当前 root / pair4
当前阶段观察
left_inverted / left—
right_inverted / right—
当前不变量
动画中不可替代的信息
当前 root / pair4
已完成局部变换0
引用修改 / 比较数0
调用栈深度0
当前层序 / 结果[4,2,7,1,3,6,9]