D
AI 学习系统RuntimeScope
主线课程算法实验台面试专题代码实验台8 周冲刺
RuntimeScope/算法实验台/56 天打卡/141 题/LC226
题型地图56天全屏141题

当前：LC226 · 翻转二叉树 · 首次出现于 Day 16 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC217LC230 →
88 / 141回到 Day 16 卡片141 题索引

LC226 · 翻转二叉树 · 递归 + 二叉树镜像教学

这道题想让我们做什么？

给你一棵二叉树，把它变成镜像树。所谓镜像，不是修改节点值，而是对每个节点交换它的左孩子和右孩子（交换 left / right 指针）。

原树
      4
    /   \
   2     7
  / \   / \
 1   3 6   9
→
翻转后（镜像）
      4
    /   \
   7     2
  / \   / \
 9   6 3   1
先搞懂三个概念
① 二叉树是什么

一棵树，每个节点最多有两个孩子：左孩子 left 和右孩子 right。没有孩子的节点叫叶子；空位置用 nil（空指针）表示。

② 翻转到底翻什么

不是交换节点里的数字，而是交换左右两个指针。一行就能表达：root.Left, root.Right = root.Right, root.Left。

③ 为什么需要递归

根节点换完，只保证第一层翻转；左子树和右子树内部也要继续翻。让每个节点都执行同一套规则——这正是递归在做的事。

核心 · 翻指针不翻值

镜像 = 对每个节点交换它的左孩子和右孩子。不是改值，而是改树的结构（left/right 指针互换）。

  • · 翻转翻的是每个节点的 left / right 指针，不是节点里的数字。
  • · 只交换根节点，只完成了第一层；7 和 2 的子树内部还是旧顺序。
  • · 每个节点都执行同一套规则：先换自己的左右孩子，再递归翻转两棵子树。
  • · 空节点（nil）直接 return，这就是递归的终止条件。
每个节点都执行的四条规则
  • root == nil → return nil
  • root.Left, root.Right = root.Right, root.Left
  • invertTree(root.Left)
  • invertTree(root.Right)
为什么用递归：每个节点都做同一件事
  1. 1.对当前节点：先交换它的 left 和 right。
  2. 2.再把“翻转左子树”“翻转右子树”这两个一模一样的小问题交给递归。
  3. 3.一路递归到 nil 触底返回，调用栈逐层弹空，整棵树就翻完了。
1/10 · 读题
10 步分镜：
Step 1读题

目标：把整棵树变成它的镜像

给你一棵二叉树，把它变成镜像树。所谓镜像，不是修改节点里的数字，而是对每个节点交换它的左孩子和右孩子。上方对比图里：根 4 不动，但它的左右两边整体对调，而且每一层都要对调。

  • 镜像 = 对每个节点交换它的左孩子和右孩子。不是改值，而是改树的结构（left/right 指针互换）。
  • · 翻转翻的是每个节点的 left / right 指针，不是节点里的数字。
  • · 只交换根节点，只完成了第一层；7 和 2 的子树内部还是旧顺序。
  • · 每个节点都执行同一套规则：先换自己的左右孩子，再递归翻转两棵子树。
  • · 空节点（nil）直接 return，这就是递归的终止条件。
为什么

镜像 = 对每个节点交换它的左孩子和右孩子。不是改值，而是改树的结构（left/right 指针互换）。

当前发生了什么

当前节点交换栈深(=树高)栈顶动作
——0[]读题输入 [4,2,7,1,3,6,9]
工作树 · 实时翻转·L / R = 左右指针
4271369invertTree 规则终止：root == nil交换 left / right递归左子树递归右子树

递归调用栈 · 当前调用链

（空栈）

栈最深 = 树高 h ⇒ 空间 O(h)

Go · invertTree
1func invertTree(root *TreeNode) *TreeNode {
2    if root == nil {
3        return nil
4    }
6    root.Left, root.Right = root.Right, root.Left
8    invertTree(root.Left)
9    invertTree(root.Right)
11    return root
12}
本题最大误区：只交换根节点够不够？
✗ 只换根（只翻第一层）
      4
    /   \
   7     2
  / \   / \
 6   9 1   3

根这层对了，但 7、2 的孩子还是旧顺序（6,9 / 1,3）。

✓ 每个节点都换（完整翻转）
      4
    /   \
   7     2
  / \   / \
 9   6 3   1

递归到 7、2 也交换：9,6 / 3,1，整棵树才是镜像。

Go 代码逐行解释
  • L2/3root == nil：递归终止条件，空树 / 空节点直接返回 nil。
  • L6root.Left, root.Right = root.Right, root.Left：交换当前节点的左右孩子（指针，不是值）。
  • L8invertTree(root.Left)：翻转交换后的左子树。
  • L9invertTree(root.Right)：翻转交换后的右子树。
  • L11return root：返回翻转后的根节点。
为什么这样一定对（归纳）
  1. 1.对于空节点 nil：不需要翻转，直接返回（终止条件）。
  2. 2.对于当前节点：我们已经交换了它的左右孩子。
  3. 3.对于左右子树：递归函数会对它们做同样的事。
  4. 4.于是每个节点都会被处理一次，且只处理一次。
  5. 5.每个节点都完成左右交换后，整棵树自然就是镜像树。
复杂度
时间
O(n)
空间
O(h)

每个节点恰好被访问、交换一次，n 为节点总数。

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

别写成空间 O(1)：递归调用栈的深度就是树高 h，最坏 O(n)。

面试可以直接背的答案

这题本质是对每个节点交换左右子树。二叉树天然适合递归：对于当前节点，先交换 left 和 right，然后递归翻转交换后的左右子树。递归终止条件是 root == nil。每个节点只访问一次，所以时间复杂度 O(n)。递归栈深度取决于树高，所以空间复杂度 O(h)，最坏 O(n)。

常见误区
误区 1：只交换 root.Left 和 root.Right 就结束

错。这样只翻转了第一层，7 和 2 的子树内部还是旧顺序。必须递归处理每个节点。

误区 2：以为要交换节点值

错。题目要求改变树结构，交换的是左右孩子指针，不是节点里的数字。

误区 3：忘记 root == nil

错。递归必须有终止条件，否则空指针会越界。空节点直接 return nil。

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

递归调用栈不是免费的，深度等于树高，应写 O(h)，最坏 O(n)。