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

一道被无数人拿来当门面的题看似简单却因为一个著名事件在网上被反复讨论——翻转二叉树。在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. 对比不同解法该选哪一种把递归前序、后序和迭代层序、前序栈版本都写完之后可以对它们做一个横向对比。为了方便查阅我用一张表来整理解法实现思路时间复杂度空间复杂度代码复杂度适用场景递归前序先交换再递归处理子树O(n)O(h)低日常刷题、面试默认写法递归后序先递归处理子树再交换O(n)O(h)低逻辑最安全避免中序陷阱迭代层序队列逐层处理每个节点O(n)O(w)中树很深时避免递归栈溢出迭代前序栈栈模拟前序遍历O(n)O(h)中想用DFS又不想递归时迭代后序栈标记法模拟后序O(n)O(h)高进阶练习加深递归理解其中 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题就是一个特别好的练手对象简单、高频、能覆盖递归和迭代两种核心能力。把这道题玩明白之后的树相关题目你会感觉自己像开了个加速器。