作为常刷LeetCode的人我太清楚“翻转二叉树”这道题的地位了。它在Hot100里属于一眼看上去没什么存在感的简单题但在技术圈内却因为一段“Homebrew作者被Google面试刷掉”的段子而自带话题度。段子的真假且不论题本身值得掰开揉碎讲一讲——它的难点不在代码量而在你能不能真正理解递归的调用过程和二叉树的结构变换。今天这篇就认真聊聊226这道题从题面理解、递归解法、迭代解法到衍生变形把这道“简单题”挖透。1. 先把题目审透“翻转”到底在翻转什么1.1 题面描述与示例原题给的是一个二叉树的根节点root要求返回翻转后的二叉树。所谓翻转就是把每一个节点的左右子树互换。举例来说输入 4 / \ 2 7 / \ / \ 1 3 6 9 输出 4 / \ 7 2 / \ / \ 9 6 3 1这个示例看下来直观感受是整棵树左右镜像了一下。但严格来说题目要求的是以每个节点为单位做左右孩子交换并不要求整棵树在空间上呈现严格的镜像对称。当然实际效果是一致的因为当所有节点的左右孩子都交换后整体自然就是水平翻转的结果。1.2 本质拆解操作的最小单元是“节点”很多第一次接触这道题的人会走进一个误区试图整体倒置这棵树或者想重构一棵新树。但实际上算法题里对这种结构变换的通用处理思路是把问题拆到单个节点层面。对一个节点来说翻转它只需要三步拿到它的左子树拿到它的右子树交换这两个子树的位置。放到整棵树上就变成了对每一个节点都做同样的交换操作并且要保证在交换之前或之后它的子树内部也已经完成了翻转。这就天然导向了递归——每个节点的处理逻辑完全相同只是处理完自己之后还要处理孩子。1.3 这道题在Hot100里的定位Hot100中的二叉树题目一共有十来道226基本上是最基础的一道。它处于什么位置如果你连二叉树的递归遍历都没写过那226是最好的入门题如果你已经刷过不少二叉树那226适合用来检验你对递归的返回值是什么递归发生在交换前还是交换后这种细节的理解。很多人觉得这类简单题不用细看但真实面试里在226上翻车的人并不少——不是写不出而是说不清复杂度或者一追问递归和迭代的区别就卡壳。2. 递归写法每个节点的三行逻辑2.1 递归的三要素拆解写递归先想清楚三件事返回值、终止条件、每一层做什么。对于翻转二叉树返回值是翻转后的根节点。终止条件是当前节点为nil直接返回nil。每一层的处理有两种等价顺序写法一先交换再递归def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]: if not root: return None root.left, root.right root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root写法二先递归再交换def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]: if not root: return None left self.invertTree(root.left) right self.invertTree(root.right) root.left, root.right right, left return root两种写法都正确但注意一个关键点写法一在交换之后原来的右孩子变成了左孩子原来的左孩子变成了右孩子所以递归调用invertTree(root.left)实际操作的是原来的右子树。这在逻辑上没有问题——反正左右子树都要翻转先翻谁后翻谁不影响最终结果。写法二则是先把左右子树都翻好再交换位置语义上更贴近后序遍历完成交换。2.2 递归的调用过程走查以题目示例的根节点4为例用手写方式模拟写法一的执行进入invertTree(4)当前节点非空交换2和7两个孩子节点。调用invertTree(2)注意此时 2 是原来根节点的右孩子因为交换过了。对节点2交换它的左右孩子1和3。调用invertTree(1)1没有孩子交换两个None返回1。再调用invertTree(3)同理返回3。返回到第二步invertTree(2)返回节点2。继续调用invertTree(7)这一步处理的是原来根节点的左子树交换6和9最终返回7。函数结束。整个过程和一种带返回值的后序遍历非常像。这也是我想强调的一点虽然代码里写的是invertTree但递归的执行顺序其实是深度优先先走一条分支走到底再回溯。理解这一点面试的时候被问到这个递归展开是什么顺序才不会懵。2.3 递归写法为什么是这道题的“标准答案”原因很简单二叉树的定义本身是递归的。每一棵子树都是一棵独立的二叉树那么翻转一棵二叉树自然可以定义为翻转根节点 翻转左子树 翻转右子树。递归不需要你手动记录遍历到哪里了也不需要额外数据结构调用栈替你完成了状态保存。代码最短、可读性最好所以绝大多数题解默认给递归版本。提示如果面试时时间紧张直接给递归版本一般不会扣分。但如果面试官追问如果树特别深怎么办你就要意识到他是在考察递归的栈溢出风险这时候需要补一句递归深度等于树高极端情况下退化成链表会 O(n) 的栈空间可以用迭代法优化。3. 迭代写法自己维护栈和队列来模拟3.1 为什么需要掌握迭代写法递归虽简洁但有一个实际问题函数调用栈会占用系统栈空间。虽然在 LeetCode 上题目给出的树深度通常有限最坏情况也不会超过几千层但你在生产代码或性能敏感场景中没法假设输入永远那么温和。何况面试中面试官非常喜欢在简单题上加追问你能用迭代写一遍吗这时候如果只记得递归观感就会打折扣。迭代翻转二叉树的思路也不复杂核心是用显式的栈或队列模拟递归的遍历顺序在遍历过程中对每个节点执行左右子树的交换。3.2 用栈模拟前序遍历前序遍历的顺序是根 - 左 - 右我们用栈来实现def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]: 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这个写法每次弹出一个节点交换它的左右孩子然后把孩子节点压入栈中直到栈空。因为不管先压左还是先压右栈的特性都会保证每个节点都被访问到、都被交换一次所以执行顺序不影响最终结果。有人可能疑惑为什么要先交换再压栈实际上顺序无所谓你可以在入栈前先交换也可以先入栈等弹出来再交换只要保证每个出栈节点都执行了交换逻辑就行。这种灵活性正是迭代遍历框架的通用性体现。3.3 用队列实现层序遍历版本除了栈用队列按层序遍历也能做而且语义上更直白——一层一层处理每层内逐个交换from collections import deque def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]: 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层序遍历版本的执行顺序是先处理根节点再处理它的两个孩子再处理四个孙节点依此类推。由于二叉树中每个节点只会被入队一次、出队一次所以总时间同样是 O(n)。3.4 两种迭代方式怎么选面试中如果要求写迭代我通常建议先快速说一个思路再动手。栈版本更适合和递归版本做对比因为它们的本质是一样的深度优先遍历队列版本则更适合强调层序处理的场景。两种都写一遍其实花不了多少时间但对理解的帮助是实打实的——你会意识到递归和迭代只是在遍历顺序上不同翻转动作本身并没有变。实现方式数据结构遍历顺序空间复杂度递归系统栈调用栈深度优先O(h)h 为树高迭代显式栈栈深度优先O(h)迭代队列队列广度优先O(w)w 为最大层宽度4. 复杂度分析和几个容易踩的坑4.1 时间与空间复杂度时间复杂度需要访问树中的每一个节点做常数次交换所以是 O(n)n 为节点总数。空间复杂度这一点面试中经常说得太粗。递归版本的空间复杂度取决于递归深度而递归深度等于树高 h因此是 O(h)。在最坏情况下一棵平衡树的高度是 O(log n)而一棵退化成链表的树高度是 O(n)所以空间复杂度上限是 O(n)。很多答案只写O(logn)是不严谨的必须注明这是平衡树下的情况。迭代版本的空间复杂度也取决于数据结构中最多同时存储多少个节点。栈版本最坏情况同样 O(h)在上限上也能达到 O(n)。队列版本则取决于最后一层的宽度最坏 O(n)。4.2 易错点一函数返回值的忽略我第一次写这道题时犯过一个错递归调用时忽略了返回值。# 错误示范 if not root: return None root.left, root.right root.right, root.left self.invertTree(root.left) # 返回值没有接收 self.invertTree(root.right) # 返回值没有接收 return root这段代码在 LeetCode 上其实能通过因为这里的invertTree是原地修改对子树调用时虽然返回值没被使用但交换已经发生了最终返回的 root 依然是正确的翻转结果。真正有问题的写法是在递归时不修改根节点的指针而是试图把返回值赋给某个变量去构建新树那样很容易搞得一团糟。4.3 易错点二只交换左右子树的“值”而不是交换“节点”假设你写的是root.left.val, root.right.val root.right.val, root.left.val这就是典型的错误。交换 val 只换了节点存储的数字但左右子树的结构包括它们的子节点和整棵子树原封未动。正确的操作对象是root.left和root.right这两个引用通过交换引用整棵子树才会跟着移动。4.4 易错点三对空节点的处理迭代版本中很多人会写成直接无条件入栈stack [root] while stack: node stack.pop() node.left, node.right node.right, node.left stack.append(node.left) stack.append(node.right)如果某个节点的左右孩子为空None会被压入栈中下一轮循环None被弹出访问None.left立刻抛出空指针异常。所以入栈前必须判断非空或者弹出后判断if not node: continue。4.5 易错点四把“翻转”与“遍历”混为一谈还有一类错误本质上是概念不清——想翻转整棵树却只对根节点做了交换就结束了。也就是说你写的是root.left, root.right root.right, root.left然后没有继续对子树做相同操作。这只会交换根节点的两个孩子内部子树完全保持原样。翻转的定义要求对每一个节点都做这个操作所以必须配合递归或遍历框架把操作覆盖到全部节点。5. 翻转之后的进阶镜像判断、递归顺序变形与同类题串联5.1 从翻转延伸到镜像判断翻转二叉树其实可以看作求一棵树的镜像的过程。既然能求一棵树的镜像自然就能问给定两棵二叉树判断它们是否互为镜像LeetCode 第 101 题“对称二叉树”就是典型的应用一棵树是否对称等价于判断它的左子树和右子树是否互为镜像。递归写法非常优雅def isSymmetric(self, root: Optional[TreeNode]) - bool: if not root: return True return self.isMirror(root.left, root.right) def isMirror(self, left: Optional[TreeNode], right: Optional[TreeNode]) - bool: if not left and not right: return True if not left or not right: return False return (left.val right.val and self.isMirror(left.left, right.right) and self.isMirror(left.right, right.left))注意这里递归参数是交叉的左子树的左孩子要和右子树的右孩子比左子树的右孩子要和右子树的左孩子比这和翻转操作中交换左右子树的思路如出一辙。5.2 “相同的树”与翻转的对照另外一个常放在一起说的题是 LeetCode 第 100 题“相同的树”判断两棵树是否相同。翻转二叉树里的递归是左左互换、右右互换而判断相同树是左左对比、右右对比。一个是交换一个是比较但递归结构非常相似。如果这三道题100、101、226放在一起刷你会很快建立起一种条件反射看到二叉树的递归题先想清楚每一层的比较/操作对象是谁再确定递归参数和返回值。5.3 翻转与遍历框架的统一实际上翻转二叉树这道题背后还有一个更大的知识点二叉树的递归遍历框架。前序、中序、后序遍历都可以用于翻转吗前序遍历翻转先交换当前节点左右子树再递归处理子树。这就是最早给出的写法一。后序遍历翻转先递归处理左右子树再交换。这是写法二。中序遍历翻转先递归处理左子树交换左右子树再递归处理右子树。注意中序翻转时处理完左子树并交换后原来右子树跑到了左边而右边是原来的左子树已经处理过所以如果要继续递归实际递归的应该是右边这个节点。也就是说中序写法的递归处理右子树这一句同样要处理 root.left。如果你习惯性地写invertTree(root.right)就会出问题。这也是一个非常经典的隐蔽坑。# 中序翻转的正确写法易错 def invertTree(self, root: Optional[TreeNode]) - Optional[TreeNode]: if not root: return None self.invertTree(root.left) # 翻转左子树 root.left, root.right root.right, root.left # 交换 self.invertTree(root.left) # 注意此时 root.left 是原来的右子树 return root这个例子值得单独拿出来讲因为很少有人注意到中序遍历在翻转场景下的特殊之处。如果你对递归框架掌握得不够细遇到这种变形很容易翻车。我在给朋友讲解时经常拿这个当例子递归的顺序不是背下来就完事而是要顺着代码执行路径推导一遍。5.4 通过翻转题目培养的结构化思维从更广义的角度来说翻转二叉树的意义不仅是会做一道简单题它训练的是把一个整体操作拆分成子操作的能力。这种能力在后面做更复杂的二叉树题时非常有用。比如求二叉树的最大深度把整棵树的最大深度拆成左子树最大深度和右子树最大深度的最大值加一。求二叉树的最小公共祖先把整棵树的 LCA递归地拆到左右子树中去判断。路径总和系列把从根到叶是否存在 targetSum 的路径拆成左右子树上是否存在 targetSum - root.val 的路径。所有这些问题都在反复使用同一个思维范式假设子树已经处理好了我只处理当前节点和子问题结果之间的关系。226 是这个思维范式最干净、最不容易被其他无关复杂度干扰的载体所以它才会被放进 Hot100作为一个入门又重要的基础节点。刷题不要追求数量把这种简单题讲到能给别人听明白的程度才算真正吃透了。我在刷题群里的经验是能清楚解释为什么中序翻转要递归两次左子树的人二叉树递归基本没有盲区。如果你看完这篇能自己把三种遍历的翻转版本都写一遍并且走查通过这道 226 就算真正过关了。