翻转二叉树：从递归到迭代的算法实践与遍历陷阱解析

一道被无数人拿来当"门面"的题，看似简单，却因为一个著名事件在网上被反复讨论——翻转二叉树。在LeetCode Hot100题单里它排在比较靠前的位置，也是很多人刷题打卡时都会遇到的一道基础题。说句实话，这道题本身的算法难度不算高，但它的意义不仅在于考一个二叉树的翻转操作，更在于帮助梳理树的遍历方式、递归思路和非递归写法。这篇文章就以Hot100第29题的视角，把226. 翻转二叉树从头到尾拆开讲清楚，包括题目本质、递归与迭代的多种写法、中序陷阱、以及刷完之后下一步可以练什么，全部用我实际刷题时验证过的思路来讲。

1. 为什么一道"简单题"引出了这么大风波

如果你在搜索引擎里输入"翻转二叉树"，大概率会看到一段流传很广的故事：某知名开源工具的作者在面试时没有写出这道题，然后被拒绝了。这件事在开发者社区里引起了不小的讨论，也让"翻转二叉树"从一个普通题目变成了一个带有话题性的名词。

我个人的看法是：这个故事的戏剧性会让很多人低估这道题的价值。它确实简单，但简单不等于没有营养。在LeetCode Hot100里，树的结构、遍历、递归、迭代这些基本功，都有大量考查场景，而翻转二叉树恰恰是一道天然的"脚手架"题。你可以用它来验证自己是不是真的理解了树的递归遍历，也可以用它来练习如何把递归改成迭代，还可以借它来辨析"前序、中序、后序、层序"这几种遍历方式之间微妙的区别。

另一个值得注意的是，Hot100是很多人在求职准备期刷得最多的一份题单。它的编排并不完全是按数据类型严格排序的，但树相关的题目从易到难展开，翻转二叉树这种题通常被安排在"建立手感"的阶段。也就是说，这道题练的不是你怎么在面试现场秀骚操作，而是你能不能在一两分钟内写出清晰的、不出错的代码。以我的面试和辅导经验，很多候选人写得出复杂的动态规划，却会在这种看似简单的题上因为递归边界、子树保存顺序、空指针处理这些小地方翻车。这也是我为什么推荐你认真对待这道题。

简单说，这道题是检验算法基本功的试金石。如果你现在还在初级阶段，它是很好的入门练习；如果你已经刷了不少题，回过头来用多种写法实现它，也是一个不错的自查过程。我下面就从题目本身的拆解开始，一步步展开。

2. 题目拆解：翻转二叉树的本质是什么

先明确原题在做什么。输入是一棵二叉树的根节点 root，要求把这棵树翻转，并返回翻转后的根节点。所谓翻转，就是对于树中的每一个节点，都把它的左子树和右子树交换位置，然后递归地对子树也做同样的操作。

比如一棵树长这样：

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

翻转之后应该变成：

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

注意观察几个细节：

• 根节点没有变化，还是4。
• 4的左右孩子2和7交换了。
• 2的左右孩子1和3交换了。
• 7的左右孩子6和9交换了。

所以翻转操作具有明显的递归性质：处理完当前节点后，要接着处理它的左右子树。对于每个节点来说，做的事情都是一样的。

从算法分析的角度看，每个节点都会被访问一次，每次访问做常数次指针交换，所以时间复杂度是 O(n)，n 是树的节点数。空间复杂度取决于递归栈或辅助栈的深度，最坏情况下树退化成链，深度是 O(n)；平均或平衡情况下是 O(log n)。

边界条件也值得提前想清楚：

• root 为空时，直接返回空。
• root 只有一个节点时，交换左右子树后其实没有变化，返回 root 即可。
• root 只有左子树或只有右子树时，空的那一侧也要参与交换，很多初写的代码会在这里出错。

我在实际写代码时习惯先把空判断写在最前面，这样能避免后续空指针访问。对于这道题，核心其实是"访问每个节点，并交换其左右子树"，至于使用哪种遍历方式，反而各有各的趣味。

3. 递归解法：自顶向下的直觉写法

大多数人的第一反应是用递归。这个反应不是没有道理的：树本身是递归定义的，翻转一棵树也可以自然地定义为"交换根节点的左右子树，然后递归翻转左右子树"。

自顶向下的写法非常直观，伪代码是：

def invertTree(root): if root is None: return None root.left, root.right = root.right, root.left invertTree(root.left) invertTree(root.right) return root

这里面有一个必须注意的细节：交换操作必须先于递归调用。原因很简单，当你执行root.left, root.right = root.right, root.left之后，当前节点的左右子树已经互换，接下来递归的invertTree(root.left)处理的是原来的右子树，invertTree(root.right)处理的是原来的左子树。因为交换是瞬间完成的，所以递归调用读到的左右子树位置已经是交换之后的位置了，这符合我们的期望。

如果反过来，先递归后交换，也就是：

invertTree(root.left) invertTree(root.right) root.left, root.right = root.right, root.left

你会发现结果也是正确的。这其实就是后序版本的递归，因为它是先处理完两棵子树，最后再交换。这个写法在逻辑上同样成立，原因在于交换操作的两个子树都已经被分别翻转好了，最后交换的只是它们的位置。对于翻转二叉树这个问题来说，这两者的最终结果一样，因为翻转每个节点的左右子树是"局部操作"，不依赖子树内部翻转的顺序。

那为什么我还把"自顶向下"单独拿出来说？因为这是最容易理解、最不容易写错的一个版本，非常适合第一遍刷题时建立思路。很多人会觉得递归是"玄学"，其实你可以把它当成一个"假设子问题已经解决"的思维模型。写递归时只需要关注三件事：当前节点要做什么、子问题怎么传入、返回值怎么用于上一层。对于翻转二叉树，当前节点要做的就是交换两棵子树，子问题就是让左子树和右子树各自翻转，返回值就是处理完的当前节点。

我也统计过一些同学的错误写法，最典型的是只在当前节点做了交换，却忘了对左右子树递归调用；或者把变量赋值顺序写成了：

root.left = invertTree(root.right) root.right = invertTree(root.left)

这个写法是错的，因为执行第一行时root.right已经被赋给了root.left，但紧接着的第二行invertTree(root.left)读到的root.left已经变成了原来的root.right，也就是说第二行递归处理的是翻转过一次的右子树，最后的结果会变成左右子树重复。这种问题在Python里尤其容易被忽略，因为多个赋值在同一行可以规避这个坑，一旦拆开写就要注意保存临时值。

所以自顶向下的写法里，我建议要么用语言自带的多重赋值，要么显式用一个 temp 变量保存其中一个子树，再分别赋值。这种看似琐碎的小地方，反而正是面试时能体现代码习惯的地方。

4. 递归的另一种选择：后序递归为什么更优雅

前序自顶向下还是后序自底向上，这道题实际上两种都能过。后序版本长这样：

def invertTree(root): if root is None: return None left = invertTree(root.left) right = invertTree(root.right) root.left = right root.right = left return root

和后序思路配合的是一个很容易踩进去的陷阱：中序递归。因为中序遍历的顺序是"左、根、右"，有些人会觉得翻转二叉树是不是也可以"先翻转左子树，再交换左右子树，最后翻转右子树"？表面一看，好像每一步都覆盖到了，但实际写出来你会发现结果不对。看一个错误示例：

# 错误示范：中序思路的递归 def invertTree(root): if root is None: return None invertTree(root.left) # 翻转左子树 root.left, root.right = root.right, root.left # 交换 invertTree(root.right) # 翻转现在位于右侧的原左子树 return root

为什么不对？因为交换之后，root.right已经不是原来的右子树了，而是翻转过的左子树。你第二次递归处理的"右子树"，实际是已经被处理过的左子树，而原来的右子树根本没有被翻转。换句话说，有一半子树被重复处理，另一半被漏掉了。

我自己第一次刷这道题的时候，就差点被这种思路带偏。后来总结出一个判断方法：交换操作之前，你有没有把涉及的子树都"处理完毕"；交换操作之后，你是否还打算处理被交换过来的子树。如果交换之前只处理了左子树、没处理右子树，那交换之后你想处理的"右子树"就已经被换掉了，这就会出问题。

后序版本为什么能完美避开这个坑？因为它先递归处理完左右两棵子树，确保它们各自都已经是翻转完毕的状态，再交换。交换之后，不需要再对任何子树做额外处理，自然不存在"处理到了哪个子树"的困惑。

所以如果你写递归时不太确定顺序，我建议直接使用后序版本。它的安全性更高，思路也更容易说清楚：先保证子树翻转完毕，再处理当前节点的交换。如果面试时被问到"还能怎么实现"，这个后序版本也是一个很好的差异化回答。

5. 迭代写法：队列层序翻转与栈模拟递归

递归虽然好写，但很多人忽略了迭代版本。面试中如果只写出递归，有时候会被追问："如果树特别深，递归栈会爆，你怎么办？"这时候迭代写法就派上用场了。

迭代的核心思想是：用显式的数据结构（队列或栈）来代替递归时的系统调用栈。写法上可以分成两大类：广度优先（层序）和深度优先（前序/后序）。

5.1 层序遍历版本：队列实现

层序遍历版本的思路是：从根节点出发，逐层将节点入队；每次取出一个节点，交换它的左右子树，然后把它的非空孩子节点入队。当队列为空时，所有节点都完成了交换。

from collections import deque def invertTree(root): if root is None: return None queue = deque([root]) while queue: node = queue.popleft() node.left, node.right = node.right, node.left if node.left: queue.append(node.left) if node.right: queue.append(node.right) return root

这个版本的空间复杂度是 O(w)，w 是树的最大宽度。在二叉树最底层满节点的情况下，w 可以接近 n/2，所以空间占用可能会比递归版本大。但它的好处是不依赖递归深度，对极端深度的树更友好。

我喜欢用层序版本讲给初学者，因为它把"树的翻转"变成了一种"逐层处理"的直观过程。你可以在脑海里模拟一个队列：先放根进来，按层往外取，每个节点被取出来时立即交换它的孩子，再把孩子们送进队列。这个过程和广度优先遍历几乎完全一致，区别只在于遍历到每个节点时做了一次交换。

5.2 深度优先迭代版本：栈模拟

如果你希望迭代版本尽量贴近递归的逻辑，可以使用栈来模拟前序遍历或后序遍历。下面是一个前序迭代的实现：

def invertTree(root): if root is None: return None stack = [root] while stack: node = stack.pop() node.left, node.right = node.right, node.left if node.left: stack.append(node.left) if node.right: stack.append(node.right) return root

这里实际上模拟的是"根、左、右"的处理顺序：先把当前节点出栈，交换左右子树，再把左孩子和右孩子分别压栈。由于栈是后进先出的，右孩子后会先出栈，这并不影响翻转结果的正确性，因为不管以什么顺序遍历，只要每个节点都完成了一次左右子树交换即可。

还有一种思路是在迭代时使用"标记法"来模拟后序递归，做法是往栈里压入 (node, visited) 这样的二元组，第一次遇到时标记未访问，等第二次弹出时再执行交换。这个写法相对繁琐，但如果你想更深刻地理解递归与栈的关系，这是一个不错的练习方向。

我自己平时比较推荐优先掌握层序和前序这两个迭代版本，因为它们代码量少、思路清晰，覆盖了面试中常见的BFS和DFS两种考察方向。后序迭代可作为进阶练习，理解了之后对递归的理解会更上一层楼。

6. 对比不同解法：该选哪一种

把递归（前序、后序）和迭代（层序、前序栈版本）都写完之后，可以对它们做一个横向对比。为了方便查阅，我用一张表来整理：

其中 h 是树高，w 是树的最大宽度。需要说明的是，如果直接用栈模拟前序，空间复杂度是 O(h)，但在最坏情况（链状树）下 h 也可能到 O(n)。这个表格帮助你在面对不同场景时快速选择。

如果让我给你一个具体建议：笔试或面试中，最优先写递归前序或递归后序，代码简洁、不容易出错，而且能体现你理解递归思想。如果面试官追问"递归深度会不会有问题"，再补一个迭代层序版本，展示你用 BFS 解决同问题的能力，这样会比只背一种解法显得全面得多。

有一点值得注意：LeetCode 官方给出的典型解法也是递归，但实际业务开发中，二叉树的深度可能非常大。我曾经在处理一个从数据库读出的组织架构树时，就遇到过递归爆栈的情况。后来改成用栈或队列迭代处理才稳定。所以刷题时多写一个迭代版本，不只是在为面试做准备，也是在为真实工程场景累积经验。

7. 容易踩的坑：写翻转二叉树时的常见错误

这部分我重点讲实际操作中比较容易翻车的几个点。如果你是自己刷题，先别看答案，试着写一遍，再对照下面几个错误，大概率会中一两条。

7.1 直接在原树上反复交换导致的逻辑混乱

这一点在上面提到过，最典型的错误是这样的：

root.left = invertTree(root.right) root.right = invertTree(root.left)

第一行执行完后，root.left 已经指向了原来的 root.right。第二行递归调用 invertTree(root.left)，实际上处理的是原来右子树，而不是原来的左子树。最后的 root.right 被设成了处理过的"原右子树"，于是左、右子树都变成了原右子树翻转的结果，原左子树丢失。这个问题在 Python、JavaScript、Java 里都会遇到，只要你不是在同一行完成交换，就需要用一个临时变量保存一个子树。

7.2 忽略了空节点

有些人在交换左右子树时，会加一层判断，比如：

if root.left: invertTree(root.left)

这样会导致空节点没有进行递归调用，但更重要的是，如果当前节点的左子树为空，右子树非空，翻转后左子树应该变成原来的右子树。如果你因为"左子树为空"就跳过某些操作，翻转就会不完整。说白了，这道题里每个节点都要处理，不管它的孩子是否为空。

7.3 后序写法中保存变量过于冗余

后序版本里经常有人这样写：

left = invertTree(root.left) right = invertTree(root.right) root.left = right root.right = left

这个没问题。但如果写成：

root.left = invertTree(root.right) root.right = invertTree(root.left)

就是同一个坑——第二行拿到的是已经被覆盖的 root.left。这个错误非常隐蔽，因为如果树是对称的或者某些子树刚好一样，结果可能碰巧正确，让你误以为代码没问题。一旦树的结构不规则，错误就会暴露出来。

7.4 没有正确处理返回值

翻转二叉树要求返回翻转后的根节点。有些写法的返回值总是 None，或者总是 root，但没有在递归过程中把结果正确传递。如果你在递归函数里直接修改了原树，最后返回 root 一般没问题。但如果你创建了新节点，却没有把新建的子树挂到父节点上，就会导致翻转后的树缺失了大量节点。我看过一些用"新建树"思路写这道题的同学，最后返回的树只有根节点，就是因为没有在递归中正确把子结果挂回。

7.5 用中序思路递归导致部分子树未翻转

这一点前面详细讲过，这里再强调一遍：如果你选择处理完左子树后交换，再处理"右子树"，那你实际上处理的是翻转后的左子树。这是一个特别容易踩但又不容易被发现的逻辑漏洞。如果树的形状恰好比较规整，你可能还真看不出结果有问题，但一旦遇到不对称的树，就会出错。

如果你问我怎么系统性自查，我有一个小技巧：翻转完一棵树后，用层序遍历打印出来，再和期望的结果对比。如果两个子树的值序列对不上，先检查交换顺序，再看递归顺序。这类小技巧在简单题上练熟了，后面刷复杂题时排查 bug 会快很多。

8. 刷完这道题后，建议紧接着练习哪些题

我先说个小建议：不要把226题当成一道孤立的题目刷完就完。树相关的题目在Hot100里形成了一个"题链"，很多题目之间思路是相通的。翻转二叉树这个操作，本质上就是"遍历每个节点并改变左右孩子指针"。一旦掌握了这个模式，下面几类题都会顺很多。

8.1 对称二叉树

这道题考察的是判断一棵树是否关于根节点对称。实现上虽然不是在翻转，但你会递归地比较左子树的左孩子和右子树的右孩子，以及左子树的右孩子和右子树的左孩子。理解了几种遍历顺序和递归结构之后，对称二叉树的递归判断会变得很清楚。

8.2 相同的树

这道题判断两棵树是否完全一样。递归写法会让"两棵树同步遍历"这个想法变得自然，和翻转二叉树配合在一起练，能加深你对"同一棵树的多个子树之间如何建立联系"的理解。

8.3 另一棵树的子树

这道题是"相同的树"的延伸，思路是遍历主树的每个节点，判断以该节点为根的子树是否和给定的子树相同。刷完翻转二叉树后，你对"以某个节点为根处理整棵子树"这种递归模式会很敏感，遇到这题时会更从容。

8.4 二叉树的最大深度/最小深度

这两道题也是Hot100的重要成员。翻转二叉树要求你理解递归的返回值，而深度类问题要求你递归地返回子树深度。两者的思想有很多重叠。如果你能在翻转二叉树时明确知道每一层递归返回的是什么，深度类题目基本不会卡壳。

我个人的刷题节奏是，以226题为起点，把上面这类树的基础题在两天内集中练一遍，效果比每天只刷一道题好很多。因为它们的核心模式都围绕着树的遍历和递归，练习密度上去之后，很多代码结构会形成肌肉记忆。

9. 我的个人体会和一个小技巧

刷这道题的过程中，我自己最大的体会是：一道题的简单不代表没有东西可挖。在你已经会了某一种写法之后，试着用不同的遍历方式重写一遍，收获远比重复做五六道同难度的新题更大。

分享一个我经常用的验证小技巧：翻转二叉树后，不要只盯着返回值看LeetCode给出的示例，实际在本地跑的时候，可以自己写一个层序遍历打印函数，把翻转前后的树打印成列表形式。例如前面那棵树翻转前打印出来是 [4, 2, 7, 1, 3, 6, 9]，翻转后是 [4, 7, 2, 9, 6, 3, 1]。这样一眼就能看出每一层是否交换正确，排查也很快。

如果你用的是Python，还可以利用根节点的左右子树交换后马上打印当前节点，直观地看到递归的执行路径。这些小技巧对初学者熟悉递归的调用过程特别有帮助。

最后，如果你正在刷LeetCode Hot100，我的建议是不要急着追求刷题数量，把少数经典题的多种解法吃透，比泛泛刷很多题更重要。226题就是一个特别好的练手对象：简单、高频、能覆盖递归和迭代两种核心能力。把这道题玩明白，之后的树相关题目，你会感觉自己像开了个加速器。