企业官网建设流程全解析

原题 226：Invert Binary Tree。你要是刷题超过两周，不可能没见过它。题目本身只有一句话：给一棵二叉树，把每个节点的左右子树交换。很多人第一次看这道题的反应是“就这？”，但它偏偏是面试里出镜率极高的一道二叉树题，原因是它能把递归、栈、队列、BFS、DFS这些基础考点全串起来。今天这篇把翻转二叉树的六种实现方案一次讲透，包括递归前序遍历、递归后序遍历、迭代前序、迭代层序、迭代中序变体和双栈后序，每种都有可运行的 Java 代码和踩坑说明。适合同学们刷题练手、准备技术面试，也适合想系统梳理二叉树遍历的读者。

1. 把题目先拆成一句人话

1.1 题目长什么样

原题描述很简单：给你一棵二叉树的根节点 root，翻转这棵二叉树，返回根节点。示例大概是这样的：

翻转前：

4 / \ 2 7 / \ / \ 1 3 6 9

翻转后：

4 / \ 7 2 / \ / \ 9 6 3 1

看起来整棵树像照了镜子，每个节点的左右孩子都互换了一次。

1.2 题目的本质是什么

很多人以为翻转二叉树是“把整棵树旋转 180 度”，这个理解不准确。树是我们抽象的存储结构，所谓翻转，本质是对每个节点执行一次左右指针交换。也就是说，只要某个节点存在，就把它的 left 和 right 对调，然后递归或迭代地把所有节点都处理一遍。

所以这道题真正考的，不是翻转这个动作本身，而是你熟不熟悉二叉树的遍历。因为翻转是一个“访问节点时要做的事”，把它放进前序、后序、层序、甚至中序框架里，都能完成同样的目标。差别只在于代码结构和面试时的表达方式。

1.3 为什么它这么出名

这题在算法圈子里有一层特殊的滤镜。好多年前，某位挺知名的开发者公开发了一条动态，说自己面试时在一道二叉树翻转题上翻了车，从那以后，“翻转二叉树”就成了段子，也成了无数人刷题旅程的必经站。这种热度让它在各种面试题库里排名一直很靠前。

从技术角度看，它也确实很适合当面试题。题干短、入口低，但能很快试探出一个人对递归出口、指针操作、栈和队列的基本功。基础不扎实的人，很容易在“交换之后往哪边走”这种细节上栽跟头。下面这六种方案，我按照从易到难的顺序展开。

2. 六种方案先过一遍脑

2.1 前置准备：TreeNode 定义

后面的所有代码，都用这个最基础的二叉树节点定义：

public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } } ### 2.2 六种方案速览表 | 方案 | 遍历方式 | 核心思路 | 空间复杂度 | 适合场景 | | --- | --- | --- | --- | --- | | 一：递归前序 | 根左右 | 先交换当前节点，再递归左右 | O(h)，h 为树高 | 面试首选，最直观 | | 二：递归后序 | 左右根 | 先递归左右，再交换当前节点 | O(h) | 理解递归时补充练习 | | 三：迭代前序 | 根左右 | 显式栈模拟系统栈 | O(n) | 面试追问不用递归时第一反应 | | 四：迭代层序 | 一层层 | 队列 BFS，逐层出队交换 | O(n) | 展示 BFS 基本功 | | 五：迭代中序变体 | 左根右 | 在中序框架里做特殊指针处理 | O(n) | 进阶理解，不建议现场优先写 | | 六：双栈后序 | 左右根 | 两个栈配合，弹出时交换 | O(n) | 顺带复习非递归后序遍历 | 这里 h 是树的高度，最坏情况下树退化为链，h 等于 n。 ### 2.3 选型逻辑一句话 面试时我一般这么建议：先写递归前序，因为代码最短、思路最好讲；如果面试官追问“递归会不会爆栈”，立刻切到迭代层序，一句“用队列做 BFS”就能把话题接住。至于迭代中序和双栈后序，属于自己练题时加深理解的方案，现场写容易绕晕。 ## 3. 方案一：递归前序，最稳妥的标准答案 ### 3.1 递归前序的思路 递归前序的核心是“先处理自己，再处理孩子”。放到这题里，就是： 1. 如果当前节点是 null，直接返回。 2. 交换当前节点的 left 和 right。 3. 递归处理新的左子树。 4. 递归处理新的右子树。 这里要注意，交换之后，当前节点的 left 已经不是原来的 left，而是原来的 right。但递归函数对所有非空节点都会执行一次交换，所以处理顺序并不会影响结果的正确性。 ### 3.2 代码实现 ```java public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.left); invertTree(root.right); return root; }

代码没有多余操作，核心就是那三行交换逻辑。

3.3 递归前序的执行轨迹

用示例树跑一遍：

• 进入 invertTree(4)，交换 4 的左右，4.left 变成 7，4.right 变成 2。
• 递归处理 7，交换 7 的左右，7.left 变成 9，7.right 变成 6。
• 递归处理 9，它是叶子节点，交换左右后返回。
• 递归处理 6，叶子节点，交换后返回。
• 回到根节点，递归处理 2，交换 2 的左右，2.left 变成 3，2.right 变成 1。
• 递归处理 3 和 1，叶子节点依次返回。

整个过程是典型的自顶向下：根先动手，再一层层往下推进。

3.4 递归前序的两个边界细节

第一个细节是 base case。很多人会漏掉 root == null 的判断，或者判断位置放错，导致空指针异常。这题里 null 的判断必须放在最前面，因为后续操作直接访问 root.left。

第二个细节是交换的顺序。递归前序是先交换再递归，递归后序是先递归再交换，两者都能得到正确结果。我见过有同学在递归前序里写成“先递归左、再交换、再递归右”，这就是递归中序的写法，在翻转题里会出问题，后面我专门解释。

4. 方案二：递归后序，优先处理子树的对称写法

4.1 递归后序的思路

递归后序的思路和前序刚好反过来：先把左右子树全部翻完，再处理当前节点。也就是：

1. 如果节点是 null，返回 null。
2. 递归翻转左子树。
3. 递归翻转右子树。
4. 交换当前节点的 left 和 right。
5. 返回当前节点。

这样写的好处是，当你交换当前节点时，它的左右子树内部已经全部处理完毕，逻辑上更“干净”。

4.2 代码实现

public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } invertTree(root.left); invertTree(root.right); TreeNode tmp = root.left; root.left = root.right; root.right = tmp; return root; }

4.3 前序和后序，到底该用哪个

两种递归写法的时间复杂度都是 O(n)，每个节点访问一次。空间复杂度也相同，递归栈深度取决于树的高度。实际工程里没有本质区别，选哪个纯粹看个人习惯。

但我建议你在面试时优先讲递归前序，因为它和目标动作“交换”贴合得最紧密，说服力最强。后序写法更适合作为“其实我还能换个顺序写”的加分项。如果面试官问你“中序递归行不行”，这时候就要小心了，直接写标准中序递归会翻车，原因我放在最后的避雷清单里讲。

5. 方案三：迭代前序，用显式栈代替系统栈

5.1 为什么要会迭代写法

面试官在递归方案之后，大概率会接一句：“如果树特别深，递归会不会有问题？”Java 里递归深度过大时可能触发栈溢出，所以迭代写法是必须准备的答案。

迭代前序的思路很简单：自己准备一个栈，模拟系统调用栈。进入节点后先交换，再把子节点按合适的顺序压栈。

5.2 代码实现

public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return root; }

5.3 压栈顺序为什么要反过来

栈是先入后出。为了让左子树先被处理，我在压栈时必须先把 right 压下去，再把 left 压进去，这样下一次弹栈弹出的就是 left。

这里要特别注意：当前节点完成交换之后，它的 left 已经变成了原来的 right。所以代码里的node.left和node.right都是交换后的新子树，不要拿交换前的旧指针去压栈，否则会漏节点。

5.4 迭代前序的常见错误

常见错误有两个。一个是只压左右孩子中的一个，比如只压node.left，导致原右子树里的节点没被访问到。另一个是压栈顺序写反，虽然最终结果大概率还是对的，因为每个节点都会被处理，但遍历顺序会变成根右左，面试官如果较真，会追问“你到底是不是前序”，容易露怯。

6. 方案四：迭代层序，BFS 一行一行翻

6.1 层序翻转的思路

层序用的是队列。BFS 的特点是一层一层往外扩，我只需要把“访问节点”的动作替换成“交换节点”，就能完成整棵树的翻转。

流程是：

1. 根节点入队。
2. 弹出队首节点，交换它的左右孩子。
3. 把交换后的左孩子、右孩子依次入队。
4. 重复直到队列为空。

6.2 代码实现

public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } return root; }

6.3 层序方案的运行轨迹

还是用示例树走一遍：

• 队列初始为 [4]。
• 弹出 4，交换左右，4 变成左 7 右 2，队列变为 [7, 2]。
• 弹出 7，交换左右，7 变成左 9 右 6，队列变为 [2, 9, 6]。
• 弹出 2，交换左右，2 变成左 3 右 1，队列变为 [9, 6, 3, 1]。
• 后续弹出的全是叶子节点，交换后不再入队。

可以看到，BFS 是一层层“平推”下去，和前序递归那种“一条路走到黑”的节奏完全不同。如果面试官让你画一下过程，层序其实最好画，因为它和自然语言描述几乎一致。

6.4 层序的空间复杂度

层序的空间复杂度是 O(n) 还是 O(w)，取决于你怎么算。严格来说，队列里最多同时存放一层的节点，也就是树的宽度。最坏情况下，一棵完全二叉树的最后一层节点数约等于 n/2，所以业界通常直接说最坏空间复杂度 O(n)。面试时你可以回答“队列最多存一层节点，空间 O(n) 级别”，会更严谨。

7. 方案五：迭代中序变体，最容易翻车的那版

7.1 标准中序迭代为什么不能直接套

标准中序迭代的框架是：

while (node != null || !stack.isEmpty()) { while (node != null) { stack.push(node); node = node.left; } node = stack.pop(); // 处理当前节点 node = node.right; }

如果“处理当前节点”是交换左右孩子，那么交换之后，node.right已经变成了原来的 left。而原来的 left 刚刚已经被压栈访问过了，继续执行node = node.right会再次处理已经翻过的子树，造成重复处理，甚至死循环。

7.2 改造版本代码

想让中序框架跑通，需要在弹出节点后改变前进方向：不往右走，而是往“新的左”走。因为交换之后，原来还没处理的右子树已经被放到了左边。

public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode node = root; while (node != null || !stack.isEmpty()) { if (node != null) { stack.push(node); node = node.left; } else { node = stack.pop(); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; // 关键点：交换后向右走会重复处理，必须向左走到新左子树 node = node.left; } } return root; }

7.3 怎么跟面试官解释这个变体

你可以这样解释：标准的左根右框架里，处理完根节点之后应该去右子树，但在翻转变体里，根节点交换完，右子树变成了已处理完的旧左子树，而旧右子树被放到了左边，还没处理，所以继续处理“新左子树”才是正确路线。

这种写法能跑通，也能通过全部测试用例，但我建议面试中不要优先写。原因很简单：解释成本太高。面试官听着容易绕，你写着也容易乱。它更适合作为你理解“遍历顺序和指针变化关系”的进阶练习，而不是用来展示的核心方案。

8. 方案六：双栈迭代后序，遍历全家桶凑齐

8.1 双栈后序的思路

后序遍历的顺序是左右根。非递归实现方式很多，我推荐双栈法，因为它逻辑清晰，不容易写错。

第一个栈 s1 负责临时存储节点，第二个栈 s2 负责记住最终的处理顺序。s1 弹出一个节点后压入 s2，然后把它的左孩子和右孩子依次压入 s1。由于 s2 是栈，最终从 s2 弹出来的时候，顺序正好是左、右、根。在这个弹出的瞬间完成交换，每个节点恰好交换一次。

8.2 代码实现

public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Deque<TreeNode> s1 = new ArrayDeque<>(); Deque<TreeNode> s2 = new ArrayDeque<>(); s1.push(root); while (!s1.isEmpty()) { TreeNode node = s1.pop(); s2.push(node); if (node.left != null) { s1.push(node.left); } if (node.right != null) { s1.push(node.right); } } while (!s2.isEmpty()) { TreeNode node = s2.pop(); TreeNode tmp = node.left; node.left = node.right; node.right = tmp; } return root; }

8.3 双栈方案的执行过程

拿示例树验证一下逻辑。s1 初始 [4]，弹出 4 压入 s2，s1 压入 2 和 7，s1 变成 [2, 7]（栈顶是 7）。弹出 7 压入 s2，s1 压入 6 和 9，s1 变成 [2, 6, 9]。弹出 9 压入 s2，s1 继续弹出 6、2、1、3，最终 s2 从栈顶到栈底的顺序是 1、3、6、9、7、2、4，也就是后序的左右根顺序。交换过程在弹出 s2 时完成，结果自然正确。

这种写法虽然代码不算最短，但它一举两得：既解决了翻转问题，又复习了非递归后序遍历。我在刷题阶段很喜欢用它做拓展训练。

9. 复杂度对比与面试时怎么选

9.1 六种方案的复杂度总结

时间上所有方案都是 O(n)，因为每个节点都要被访问并交换一次。空间上递归方案看树高，迭代方案看节点数量，层序方案看树的宽度。

9.2 面试时的建议节奏

我建议按这个节奏组织回答：

1. 先写递归前序，用 30 秒解释“交换当前节点，再递归子树”。
2. 如果面试官问“递归深度太深怎么办”，再写迭代层序，说明队列的 FIFO 特性。
3. 如果面试官还想考察非递归深度遍历，把迭代前序写出来，压栈顺序讲清楚。

这样一层层递进，既展示了广度，又不会让核心思路被复杂变体抢走风头。把迭代中序和双栈后序放在面试第一版，很可能会因为解释不清而被扣印象分。

10. 我踩过的坑和给你的避雷清单

10.1 递归中序为什么不能直接写

这是我见过同学们踩得最多的坑。直接写：

// 错误示例 public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } invertTree(root.left); TreeNode tmp = root.left; root.left = root.right; root.right = tmp; invertTree(root.right); return root; }

这个写法的问题在于：交换之后，root.right实际上是原来的 left，而原来的 left 已经被翻转过一次了，递归调用invertTree(root.right)会再次翻转它，导致部分子树被翻两次，结果归位，整体出错。理解这个坑之后，再看前面迭代中序变体的那一套“往左走”的逻辑，就能明白为什么不能按常规中序的老路走。

10.2 迭代前序的入栈顺序口诀

我自己的口诀是“先压右，再压左，弹出来就是左”。这是栈的特性决定的。如果写反，遍历顺序就不再是前序。虽然这题的结果依然正确，但面试里的追问会让你很难自圆其说。

10.3 交换操作最好用临时变量

交换左右孩子，代码是固定的三行：

TreeNode tmp = node.left; node.left = node.right; node.right = tmp;

不要因为偷懒而省略 tmp。Java 里直接写node.left = node.right; node.right = node.left;会把 node.right 变成已经被覆盖的值，最后左右指向同一个节点。这种错误在紧张的面试条件下很容易出现，写完之后再对照一遍，三行交换是最低成本的检查。

10.4 面试表达模板

如果让我给你一个可以直接套用的表达，我会这样说：

“翻转二叉树的核心是对每个节点交换左右孩子。我可以用递归前序实现，先交换当前节点，再递归处理左右子树。如果考虑树深度，可以改成层序遍历，用队列依次处理每一层。两种方案时间复杂度都是 O(n)。”

这段话既点明了方案，也把复杂度和迭代思路全部带上了。后面再根据面试官的方向去展开，节奏基本不会乱。

10.5 进阶提示：统一写法理解遍历

有一定基础之后，你可以尝试用“标记法”这种统一迭代方式去理解前中后序的区别：给每个待处理的节点打一个访问标记，遇到未标记的节点就压栈并标记，遇到已标记的节点就执行交换。这种方法能让你把所有遍历框架串起来，以后遇到二叉树的序列化、搜索、路径等问题，思路会清楚很多。

最后再分享一个小技巧：刷这道题不要只背代码，把题目当作一次遍历基本功验收。今天翻开是前序，明天就默写一遍后序，后天再试试层序。这比反复做新题更能巩固手感。翻转二叉树不是一道要背的题，它是一把能帮你理清二叉树遍历的钥匙。