LeetCode 226 这道翻转二叉树在算法面试里可以说是“抬头不见低头见”的经典题。题目本身不难难的是你能不能把它回答得漂亮——递归前序遍历、后序遍历、中序遍历、迭代栈、层序遍历队列加上各种变体至少能写出六种实现方案。很多候选人能写出来一种但被追问“换一种遍历方式怎么写”“递归转迭代怎么做”“空间复杂度是多少”时就卡住了。这篇文章就是把这道题彻底掰开揉碎从题目拆解、六种实现方案、复杂度对比到面试表达技巧、避坑细节、同类题迁移一次讲透。不管是准备面试的开发者还是想巩固二叉树基本功的读者这份解析都能直接拿来用。1. 翻转二叉树到底在考什么先别急着写代码1.1 原题的正确读法题目描述其实很短给定一棵二叉树的根节点root翻转这棵二叉树并返回其根节点。什么叫“翻转”就是把这棵树中每一个节点的左右子树都交换。举个具体例子。原始树长这样4 / \ 2 7 / \ / \ 1 3 6 9翻转之后变成4 / \ 7 2 / \ / \ 9 6 3 1注意看根节点 4 的左右孩子 2 和 7 交换了位置第二层的 2 节点它的左右孩子 1 和 3 也交换了7 节点的左右孩子 6 和 9 也交换了。本质上对树里的每一个节点都执行一次“交换左右孩子”的操作。很多新手一开始会误以为“翻转”是把整层节点倒序排列然后试图按层去反转数组。这个理解不完全错但不够本质。按层反转在完全二叉树里恰好能得到正确答案但一旦树不是满的就会出问题。正确的思路必须落在“每个节点”上而不是“每一层”上。1.2 一道简单题为什么能区分面试者水平我见过不少面试现场候选人拿到这题不到一分钟就写出了递归前序遍历版本代码很干净测试样例也过了。但如果面试官继续问“这个递归的深度最坏是多少”“如果不让用递归怎么写”“层序遍历能不能实现队列里应该放交换前还是交换后的孩子”“为什么中序递归版本容易写错”能一路答下来的人明显是真正理解二叉树遍历模板的答不上来的多半是背过几道题、没形成体系。这道题的价值就在这它看似简单却能考察开发者对二叉树遍历的三种递归顺序、迭代与递归的转换、DFS 与 BFS 的本质差异、空间复杂度的估算等多项基本功。一道题背后藏着一整块知识网络。1.3 一切操作的最小单位我们反复强调翻转只是在每个节点上做同一个动作node.left, node.right node.right, node.left所以解题的核心就变成了怎么在遍历二叉树的过程中让每个节点都执行一次这个交换操作。遍历二叉树有两条大路线深度优先搜索DFS递归前序/中序/后序、手动栈迭代广度优先搜索BFS层序遍历这两条路线每一种都能走到每个节点因此每一种都能完成翻转。这也是“六种实现方案”这个说法的来源。接下来的内容我们把六种方案一个一个拆开代码都给出细节和坑也都不放过。2. 递归三兄弟前序、后序、中序的写法和那个经典大坑2.1 递归前序遍历先交换再往下走这是最直观、也是大多数人第一反应能写出来的版本。def invertTree(root): if not root: return None # 先交换当前节点的左右孩子 root.left, root.right root.right, root.left # 再去翻转左子树和右子树 invertTree(root.left) invertTree(root.right) return root逻辑顺序很清晰处理当前节点交换→ 递归左子树 → 递归右子树。因为当前节点的交换已经完成后面无论递归到哪个子树都不会再影响交换结果。这个版本有个值得讨论的细节交换之后再递归传入invertTree(root.left)时这个root.left已经是原来交换进来的节点了。比如根节点的左孩子变成了原来的右孩子。这会不会导致错误不会。因为我们的目标本来就是让“每一个节点都交换一次”。原来的右孩子现在位于左位置作为一棵子树的根节点它同样需要被翻转递归进去操作它即可。原来的左孩子被换到了右位置它也会被递归到。所以前序递归是安全的左右子树的递归顺序甚至可以反过来结果都一样。2.2 递归后序遍历先把子树翻好再翻自己后序递归的思路是先递归翻转左子树 → 再递归翻转右子树 → 最后交换当前节点的左右孩子。def invertTree(root): if not root: return None # 先翻转左右子树 if root.left: invertTree(root.left) if root.right: invertTree(root.right) # 最后交换当前节点的左右孩子 root.left, root.right root.right, root.left return root我个人在实际刷题时其实更推荐优先写这个版本。为什么因为它天然符合“自底向上”的递归思维先把孩子的问题解决了再处理自己的问题。从语义上讲我们想翻转整棵树就可以定义成“把左子树翻好把右子树翻好再把它们交换位置”。这是最接近问题描述本身的递归定义面试时这样解释表达也最自然。注意这里加了一个if root.left的判断。其实不加也没问题递归函数内部对None会自动返回但加上判断能减少一次函数调用代码逻辑上也更显性。当然为了简洁也可以去掉判断def invertTree(root): if not root: return None invertTree(root.left) invertTree(root.right) root.left, root.right root.right, root.left return root两种写法都对面试时写简洁版就好判断条件可以在解释时提及。2.3 中序递归最容易翻车的一个版本中序递归的“标准框架”是左 → 中 → 右。套到翻转问题上自然有人会写成def invertTree(root): if not root: return None invertTree(root.left) # 先翻左子树 root.left, root.right root.right, root.left # 交换当前节点 invertTree(root.right) # 再翻右子树 return root这个写法是有问题的。问题出在交换之后root.right已经不是原来那个右子树了。具体走一遍invertTree(root.left)把左子树翻转好交换root.left和root.right此时root.right指向原来的左子树root.left指向原来的右子树再执行invertTree(root.right)翻转的是“原来的左子树”。也就是说原来左子树被翻了两次相当于是又被翻回去了而原来右子树根本没有被翻。最终结果只交换了根节点左右子树内部没有被正确翻转。正确的写法是交换之后原本该处理的“右子树”已经跑到了左边所以还要继续递归root.leftdef invertTree(root): if not root: return None invertTree(root.left) # 翻转左子树 root.left, root.right root.right, root.left # 交换左右孩子 invertTree(root.left) # 此时 root.left 是原来的右子树继续翻转 return root这个“中序版本要递归两次左”的写法是很多人刷这题时踩过的最经典的坑。如果你在面试现场能把这一步主动讲给面试官听其实是很好的加分项——这能证明你不是在背模板而是真的理解每一步在干什么。2.4 递归实现的三个共性要素不管前序、中序还是后序设计递归函数时都可以归纳成三步递归出口节点为空时直接返回不做任何操作本层逻辑交换当前节点的左右孩子递归调用根据前序/中序/后序的不同把交换动作放在递归之前、之间或者之后。只要记住“交换是每个节点的本层任务”三种顺序都能写对。但中序要特别注意交换动作对后续递归节点的影响。递归版本的时间复杂度都是 O(n)每个节点访问一次空间复杂度取决于递归深度也就是树的高度。平衡二叉树是 O(log n)链状退化成 O(n)。3. 不用递归两种主流的迭代实现方案3.1 用栈模拟前序遍历手动管理系统栈递归本质上依赖系统栈。我们也可以自己准备一个栈手动控制遍历顺序这样就不会受到递归深度的限制。前序遍历的迭代模板是先压右孩子再压左孩子这样弹出的时候先处理左孩子。def invertTree(root): if not root: 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.left和node.right那么压栈的时候到底应该压交换前的孩子还是交换后的孩子仔细想想我们交换的是“当前节点的两个子树的位置”而这两个子树本身还是需要被继续翻转的。所以不管把哪个子树压进栈最终都会在后续循环中弹出并处理。压栈顺序甚至反着来也可以得到正确结果只是“先右后左”保持了前序遍历的语义代码风格更统一。这个版本的遍历顺序是深度优先空间复杂度最坏 O(n)树退化成链状平均 O(h)h 是树高。3.2 层序遍历方案用队列做 BFS逐层完成翻转层序遍历实现的思路也很直观从根节点开始一层一层往下走每个节点出队时完成自己的交换再把孩子节点入队。from collections import deque def invertTree(root): if not root: 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为什么这样能翻完整棵树因为 BFS 会访问到每一个节点每个节点出队时都完成了一次交换一个不落。如果不用deque也可以用普通列表模拟队列但千万不要用pop(0)。pop(0)的时间复杂度是 O(n)每次都会把后面所有元素往前挪一位整体复杂度会退化到 O(n²)这是层序遍历里的一个细节坑。面试时用deque是标配deque的popleft()是 O(1)。层序实现中队列里最大会同时存“某一层”的节点。对于一棵完全二叉树最大宽度约为 n/2所以空间复杂度最坏也是 O(n)。3.3 栈和队列两种迭代方案怎么选从遍历本质上讲栈版本走的是深度优先先一头扎到底再逐层返回队列版本走的是广度优先自上而下一层一层推进。两者时间复杂度都是 O(n)只是处理顺序不同。对于翻转二叉树这个问题处理顺序不影响最终结果所以两个版本都正确。面试时如果被要求“写一个非递归版本”我建议优先写层序 BFS因为写法直观不容易弄错压栈顺序deque的引入能展示你对标准库的熟悉程度层序版本天然避免了递归深度爆栈的问题。如果题目限制“不能用额外的数据结构”那就只能选栈版本甚至可以用 Morris 遍历做到 O(1) 空间不过那就属于扩展话题了普通面试很少追问到这个深度。4. 第六种方案统一栈模拟后序遍历的标记法4.1 后序遍历迭代为什么麻烦递归后序很简单但“不用递归实现后序遍历”一直是二叉树题里的一个经典难点。前序遍历的迭代很好写因为根节点最先被处理弹出即操作后序遍历要求“左右子树处理完最后处理根节点”而迭代时没法直观地知道一棵子树是否已经处理完了。传统做法有两种双栈法用第二个栈保存逆序结果代码比较绕标记法给每个节点加一个状态位第一次出栈不处理重新入栈并标记为“已见过”第二次出栈时才真正执行操作。标记法最好理解也最容易推广到前序和中序。用它来实现第六种方案正好补全了“递归四兄弟”之外的迭代后序版图。4.2 标记法代码解析我们用一个二元组(node, visited)来表示节点的状态visited为False表示第一次碰到这个节点True表示它的子树都已经处理完应该真正操作这个节点了。def invertTree(root): if not root: return None stack [(root, False)] while stack: node, visited stack.pop() if not node: continue if visited: # 第二次出栈左右子树都已翻转交换当前节点孩子 node.left, node.right node.right, node.left else: # 第一次出栈按反向顺序压栈标记当前节点为已访问 stack.append((node, True)) stack.append((node.right, False)) stack.append((node.left, False)) return root入栈顺序的推导逻辑是栈是后进先出我们希望出栈顺序是“左 → 右 → 中”。那么入栈顺序就必须反过来“中 → 右 → 左”。所以先压入标记好的当前节点再压右孩子最后压左孩子。这样下一次循环会先碰到左孩子。如果单纯为了让翻转结果正确入栈顺序并不强制要求保持后序因为左右子树翻转的先后顺序不影响最终结果。但作为一套模板记忆保持标准顺序更有价值以后处理其他“后序操作”时可以直接复用。标记法的空间复杂度同样是 O(n)但因为每个节点需要额外存一个布尔标记常数空间比前两个迭代版本略大。大多数场景下没什么影响。4.3 六种方案横向对比到这里六种方案全部集齐了。我做了一张对比表方便面试前快速回顾方案遍历方式交换时机空间复杂度代码简洁度面试推荐度递归前序DFS前序递归前交换O(h)高⭐⭐⭐⭐递归中序DFS中序左递归后交换再递归左O(h)高但易踩坑⭐⭐⭐递归后序DFS后序递归完成后交换O(h)最高⭐⭐⭐⭐⭐栈迭代前序DFS前序弹栈后交换O(h)~O(n)中⭐⭐⭐⭐层序队列BFS层序出队后交换O(n)中⭐⭐⭐⭐⭐标记法定后序DFS后序二次出栈交换O(n)中⭐⭐⭐⭐实际面试中通常只需要写出两三种核心方案即可递归后序打底层序 BFS 展示广度优先功底栈迭代展示迭代转换能力。六种全写出来当然更好但要确保每一个都能讲清楚思路而不是背代码。5. 面试作答技巧怎么把这题“表演”到位5.1 拿到题后的思考路径和表达顺序很多候选人做完这题觉得“太简单了”其实关键在于表达。我建议拿到题后按这个顺序组织思路和语言第一句点出本质“翻转二叉树其实就是遍历每个节点交换它的左右孩子所以关键是选一种遍历方式。”第二句给出方案“我优先用递归后序实现因为它的定义最贴合问题——先把左右子树分别翻转再交换当前节点的位置。”然后边说边写。写递归函数时主动说明三点空节点是递归出口直接返回本层只做一件事交换左右孩子返回值是当前子树的根节点。写完之后再补一句“这个版本的时间复杂度是 O(n)空间复杂度是 O(h)h 是树高。如果树退化成链表递归深度会达到 O(n)可能栈溢出。”这句话说出来面试官就知道你对复杂度有意识不是只会写代码。5.2 边界条件与高频错误自查清单翻转二叉树虽然简单但出错的点非常多。我整理了一份高频错误清单刷题和面试前可以对照自查空树没有处理if not root: return None必须放在函数最前面。中序递归写错右子树交换后递归的应该是left不是right详见 2.3 节的拆解。递归调用没有返回值翻转问题的递归函数必须返回当前节点的根引用否则调用方拿不到新的结构。栈迭代忘记判断空节点如果压栈前不判断node.left/node.right是否为空后面弹出空节点时去访问.left会直接报错。层序误用pop(0)普通列表的pop(0)是 O(n) 操作整个算法会退化到 O(n²)。用deque.popleft()。平行交换写成三行时少一步很多语言的数组结构可以平行交换但如果是写 Java、C 这类语言需要临时变量保存引用三步操作一步都不能省。5.3 面试官常见追问与应对参考围绕这道题面试官有几类追问出现的概率很高追问一递归转迭代怎么转直接写出栈迭代或层序队列版本并说明递归依赖系统栈迭代是手动维护栈或队列时间和空间复杂度一致但迭代不受递归深度限制。追问二能不能做到 O(1) 额外空间可以提 Morris 遍历利用节点的空指针做线索化遍历。翻转问题里只需要把遍历过程中的“访问节点并交换孩子”替换成 Morris 的动作即可。不过这种方案写起来复杂面试中属于加分项不要求必须写出来。如果没有把握可以坦诚地说“知道思路但代码比较绕我需要一点时间”企业通常更看重你怎么分析而不是硬背。追问三如果树有十万个节点哪个方案最稳优先选层序 BFS。它的空间复杂度只跟树的宽度有关不会因为树退化成链表而变成 O(h)而且完全不受递归深度影响。如果树很宽但很矮递归也未尝不可如果树很深递归可能直接栈溢出。追问四如何判断两棵树是不是互为翻转这类题目更强调整体递归思维翻转树 A和树 B 比较每个节点是否相等。本质上还是“同时遍历两棵树”的框架。6. 从 226 这道题说起一类二叉树面试题的思维迁移6.1 真正要掌握的是遍历模板把六种实现方案刷完之后你会发现翻转二叉树只是“在遍历中做一次交换操作”本身没有引入任何新算法思想。相比之下更重要的是通过这道题把**二叉树的四种遍历前序、中序、后序、层序和两种实现方式递归、迭代**练到条件反射的程度。面试中大量二叉树题都能落到这个模板上对称二叉树同时遍历左右子树判断镜面对称二叉树的最大深度后序遍历返回左右子树深度最大值加一合并二叉树同时遍历两棵树对应节点相加二叉树的最近公共祖先后序遍历根据左右子树包含情况逐层判断翻转奇数层节点层序遍历只在奇数层交换两个节点的值。这些题的核心骨架都一样选一个遍历方式在“访问节点”的位置塞入额外逻辑。226 练透之后遇到这类题能省下大量重新理解的时间。6.2 业务开发里的同类场景不要觉得二叉树只有面试用得上。我在实际业务开发中遇到过几次“遍历结构并修改字段”的场景本质上和翻转二叉树非常相似。比如前端组件库里的 JSON 树形配置后端返回的字段名不满足新版本要求需要把每个节点的name重命名为label权限系统中的菜单树需要给每个节点插入一层“父级路径”字段多级评论结构要按新规则重排子节点顺序……这些操作都是遍历一棵多叉树/JSON树在每个节点上执行固定修改。这时候如果你脑袋里只有“递归”这一个方案面对很深的数据嵌套也会担心爆栈如果你能把递归、迭代栈、层序队列都信手拈来就能根据数据规模和结构特点灵活选择方案。这就是 226 这道题在项目里的实际价值——它训练的不是“翻转”这个动作而是“对动态结构的每个节点做统一处理”的能力。6.3 刷题建议用十分钟做一次“全套输出”最后给一个我实测有效的练习方法。找一天关掉题解定时十分钟在一张空白编辑器里只靠记忆写出六种方案的完整代码递归前序、递归中序、递归后序、栈迭代前序、层序队列、标记法后序。写完之后对照四个点自查中序版本是否写了会导致“翻转抵消”的invertTree(root.right)栈迭代是否保持了正确的出栈顺序层序版本是否用了deque而不是list.pop(0)每个版本的返回值是否都是根节点。如果十分钟内六种方案都能一次通过测试用例这道题对你来说就真正过关了。以后再遇到“遍历二叉树 节点操作”的问题你会明显感觉到思路快了很多。我个人第一次做这个练习时卡在了中序递归整整五分钟因为我也是下意识写了invertTree(root.right)踩了那个最经典的坑。后来把“交换动作会影响后续递归对象”这个意识刻进脑子里才彻底弄明白为什么中序版本要递归两次左子树。这个认知比记住一份代码值钱得多。刷题切记别背代码去理解每一步变化的因果。