原题 226Invert 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 变成 74.right 变成 2。递归处理 7交换 7 的左右7.left 变成 97.right 变成 6。递归处理 9它是叶子节点交换左右后返回。递归处理 6叶子节点交换后返回。回到根节点递归处理 2交换 2 的左右2.left 变成 32.right 变成 1。递归处理 3 和 1叶子节点依次返回。整个过程是典型的自顶向下根先动手再一层层往下推进。3.4 递归前序的两个边界细节第一个细节是 base case。很多人会漏掉 root null 的判断或者判断位置放错导致空指针异常。这题里 null 的判断必须放在最前面因为后续操作直接访问 root.left。第二个细节是交换的顺序。递归前序是先交换再递归递归后序是先递归再交换两者都能得到正确结果。我见过有同学在递归前序里写成“先递归左、再交换、再递归右”这就是递归中序的写法在翻转题里会出问题后面我专门解释。4. 方案二递归后序优先处理子树的对称写法4.1 递归后序的思路递归后序的思路和前序刚好反过来先把左右子树全部翻完再处理当前节点。也就是如果节点是 null返回 null。递归翻转左子树。递归翻转右子树。交换当前节点的 left 和 right。返回当前节点。这样写的好处是当你交换当前节点时它的左右子树内部已经全部处理完毕逻辑上更“干净”。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; } DequeTreeNode 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 的特点是一层一层往外扩我只需要把“访问节点”的动作替换成“交换节点”就能完成整棵树的翻转。流程是根节点入队。弹出队首节点交换它的左右孩子。把交换后的左孩子、右孩子依次入队。重复直到队列为空。6.2 代码实现public TreeNode invertTree(TreeNode root) { if (root null) { return null; } QueueTreeNode 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; } DequeTreeNode 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; } DequeTreeNode s1 new ArrayDeque(); DequeTreeNode 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 压入 s2s1 压入 2 和 7s1 变成 [2, 7]栈顶是 7。弹出 7 压入 s2s1 压入 6 和 9s1 变成 [2, 6, 9]。弹出 9 压入 s2s1 继续弹出 6、2、1、3最终 s2 从栈顶到栈底的顺序是 1、3、6、9、7、2、4也就是后序的左右根顺序。交换过程在弹出 s2 时完成结果自然正确。这种写法虽然代码不算最短但它一举两得既解决了翻转问题又复习了非递归后序遍历。我在刷题阶段很喜欢用它做拓展训练。9. 复杂度对比与面试时怎么选9.1 六种方案的复杂度总结方案时间空间代码长度面试推荐度递归前序O(n)O(h)最短极高递归后序O(n)O(h)短中高迭代前序O(n)O(n)中高迭代层序O(n)O(n)中高迭代中序变体O(n)O(n)中低双栈后序O(n)O(n)较长中时间上所有方案都是 O(n)因为每个节点都要被访问并交换一次。空间上递归方案看树高迭代方案看节点数量层序方案看树的宽度。9.2 面试时的建议节奏我建议按这个节奏组织回答先写递归前序用 30 秒解释“交换当前节点再递归子树”。如果面试官问“递归深度太深怎么办”再写迭代层序说明队列的 FIFO 特性。如果面试官还想考察非递归深度遍历把迭代前序写出来压栈顺序讲清楚。这样一层层递进既展示了广度又不会让核心思路被复杂变体抢走风头。把迭代中序和双栈后序放在面试第一版很可能会因为解释不清而被扣印象分。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 进阶提示统一写法理解遍历有一定基础之后你可以尝试用“标记法”这种统一迭代方式去理解前中后序的区别给每个待处理的节点打一个访问标记遇到未标记的节点就压栈并标记遇到已标记的节点就执行交换。这种方法能让你把所有遍历框架串起来以后遇到二叉树的序列化、搜索、路径等问题思路会清楚很多。最后再分享一个小技巧刷这道题不要只背代码把题目当作一次遍历基本功验收。今天翻开是前序明天就默写一遍后序后天再试试层序。这比反复做新题更能巩固手感。翻转二叉树不是一道要背的题它是一把能帮你理清二叉树遍历的钥匙。