刷 LeetCode Hot 100 刷到第 37 题正好是翻转二叉树。这道题在互联网圈子里的知名度基本属于“梗”级别——Homebrew 作者当年面试谷歌被这道题挂掉的故事流传度比题目本身还高。不过梗归梗真动手写的时候很多人还是会卡在递归顺序、迭代写法这些细节上。这篇就用实际刷题的角度把翻转二叉树从题目理解、递归解法、迭代解法到常见坑位完整拆一遍顺便聊聊为什么这道简单题值得进 Hot 100。1. 题目拆解翻转二叉树到底在翻什么1.1 核心需求解析题目描述非常短给定一棵二叉树的根节点root翻转这棵二叉树并返回其根节点。所谓翻转就是把这棵树的每一个节点的左右子树都交换位置最终得到一棵与原树关于垂直中轴线镜像对称的树。举个最简单的例子。原树长这样4 / \ 2 7 / \ / \ 1 3 6 9翻转之后变成4 / \ 7 2 / \ / \ 9 6 3 1注意看根节点4没变但它原来的左子树2子节点 1、3整体被挪到了右侧原来的右子树7子节点 6、9整体被挪到了左侧。子树内部也要继续翻转比如7的左子节点6变成了右子节点右子节点9变成了左子节点。所以翻转二叉树本质上是“对每一个节点交换它的左右子节点”这个操作的递归应用。这里的关键在于必须是“每一个节点”不能只交换根节点的左右子树就完事因为子树内部的对称结构同样需要调整。1.2 边界条件与示例分析题目的输入输出约束不多只要涉及二叉树就绕不开空节点的情况如果root为空翻转后仍然为空直接返回nil或null。如果只有一个节点没有左右子节点翻转后节点本身不变但仍要正确处理。还有一个容易忽略的点题目只说了返回根节点并没有说不能修改原树。因此我们可以原地翻转直接在原树上交换左右子节点并递归处理不需要额外创建新节点。这也是这类题目的常规操作。关于返回值的理解二叉树节点通常用结构体定义例如public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } }Python 则用类定义class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right注意root传入的时候其实是引用类型递归函数如果返回一个新的根节点那么调用方需要接收返回值如果直接在原树上操作返回同一个root也可以只是要保证调用点知道这个根节点仍然有效。我个人习惯是直接返回root方便串接递归也能省去一些边角情况的判断。2. 递归解法一句话就能写出来的背后逻辑2.1 递归的终止条件与子问题拆解递归解法的代码短到很多人第一次看到会愣一下def invertTree(self, root: TreeNode) - TreeNode: if not root: return None root.left, root.right root.right, root.left self.invertTree(root.left) self.invertTree(root.right) return root这段代码的核心思想是“分而治之”如果当前节点为空没有可翻转的子树直接返回None。当前节点不为空就交换它的左右子节点。对交换后的左子树原来的右子树继续递归翻转。对交换后的右子树原来的左子树继续递归翻转。返回当前节点。这里有一个特别容易让新手困惑的点我先交换了左右子节点再递归invertTree(root.left)那这时候root.left到底指向哪实际上交换之后root.left指向原来的右子树root.right指向原来的左子树。接下来递归root.left就是把原来的右子树内部翻转一遍递归root.right就是把原来的左子树内部翻转一遍。最终每个节点都被处理到整体镜像对称就完成了。2.2 多种语言的实现与注释用不同语言写一遍加深理解。Java 版本public TreeNode invertTree(TreeNode root) { if (root null) { return null; } TreeNode temp root.left; root.left root.right; root.right temp; invertTree(root.left); invertTree(root.right); return root; }Golang 版本func invertTree(root *TreeNode) *TreeNode { if root nil { return nil } root.Left, root.Right root.Right, root.Left invertTree(root.Left) invertTree(root.Right) return root }C 版本TreeNode* invertTree(TreeNode* root) { if (!root) return nullptr; swap(root-left, root-right); invertTree(root-left); invertTree(root-right); return root; }所有语言的核心逻辑完全一致交换、递归、返回。代码里不需要记录任何临时状态也不需要像迭代法那样手动维护栈或队列因为函数调用栈本身就帮我们记录了递归路径。2.3 为什么不能先交换再递归——递归顺序的坑这里必须单独拎出来讲一个经典陷阱中序遍历的顺序翻转会出错。很多人会想既然要翻转整棵树那用中序遍历左、根、右的顺序每个节点访问时交换左右子节点不也一样吗先写出来看看def invertTree_inorder(root): if not root: return None invertTree_inorder(root.left) # 先翻转左子树 root.left, root.right root.right, root.left # 交换当前节点左右 invertTree_inorder(root.right) # 再翻转右子树 return root这段代码在多数情况下会出现问题。原因在于中序顺序下递归调用invertTree_inorder(root.left)完成之后当前节点的左子树已经被翻转过一次了此时交换root.left和root.right原来的右子树变成了新的左子树接着递归调用invertTree_inorder(root.right)但这里的root.right已经是原来翻转后的左子树这会导致部分节点被重复处理另一部分节点没被处理。举一个具体的反例。一棵树1 / \ 2 3 / 4用中序翻转法从根节点1开始先递归左子树即节点2。对节点2来说先递归它的左子树4节点4没有左右子节点递归返回后交换4的左右都是空无所谓。回到节点2交换2的左右子节点现在2的左子节点为空右子节点为4。然后递归2的右子树也就是节点4由于4没有子节点递归结束。回到根节点1交换1的左右子节点现在1的左子节点是3右子节点是2且2的右子节点是4。再递归1的右子树也就是节点2此时对2再次交换左右子节点。原本2的左为空右为4交换后左为4右为空。最终原始树变成了1 / \ 3 2 / 4看起来好像也是镜像但注意节点2的子树本来应该是镜像后的右子树这里却被处理了两次。实际测试更多节点时中序翻转容易导致一些子树没有被正确交换或者被交换了两次。本质原因是中序遍历的“左根右”顺序在交换左右子节点之后root.right的含义已经发生了变化递归的参数不再符合“原始右子树”的预期。因此最稳妥的做法是采用前序先交换再递归左右或后序先递归左右再交换避免在递归中途修改节点指向导致混淆。3. 迭代解法用队列模拟层序翻转3.1 广度优先遍历交换左右子节点递归虽然简洁但也有人嫌它有栈溢出的风险树特别深时。迭代法可以完全避免系统栈递归深度的问题用显式的数据结构来控制遍历顺序。最常见的迭代写法是广度优先遍历BFS借助队列完成。核心思路把根节点入队循环弹出节点交换其左右子节点然后把左右子节点交换后的入队继续处理下一层。代码长这样from collections import deque def invertTree_bfs(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注意这里入队的是交换后的node.left和node.right。由于已经交换过了入队的左子节点其实是原来的右子树但没关系我们接下来要处理的正是这些子树内部的节点。对每个节点都执行交换操作最终结果和递归一致。3.2 深度优先用栈实现前序与后序除了 BFS用栈做深度优先遍历DFS同样可以翻转。栈的写法有三种变体前序、后序、以及类似递归的顺序。这里给出一个前序的栈版本def invertTree_dfs(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这个版本先处理当前节点交换然后把左右子节点压栈。因为栈是后进先出所以压栈顺序无所谓先后只要两个非空子节点都进栈即可。这里本质上是在模拟递归前序遍历的行为。后序版本则可以先递归压栈右、左再出栈交换def invertTree_dfs_postorder(root): if not root: return None stack [root] while stack: node stack.pop() if node.left: stack.append(node.left) if node.right: stack.append(node.right) node.left, node.right node.right, node.left return root这个版本先分别把左右子树压入栈等它们被处理之后最后交换。其实对整棵树而言我们关心的是所有节点都被交换顺序不会影响最终结果只要保证每个节点恰好交换一次即可。3.3 复杂度对比与适用场景两种主流解法的时间复杂度都是 O(n)因为每个节点都要访问一次。空间复杂度上递归解法空间复杂度取决于递归深度最好情况平衡树为 O(log n)最坏情况链状树为 O(n)。BFS 迭代解法空间复杂度为 O(n)因为队列中最多存储一层的节点最宽的一层可以有 n/2 个节点。DFS 栈迭代解法空间复杂度为 O(n)栈中最多存储树高个节点最坏也是 O(n)。实际刷题时递归写法更短、可读性更好是面试时的首选。如果面试官追问“会不会栈溢出”再用迭代解法展示你对递归底层原理的理解。我在面试中一般先答递归然后主动补充一句“如果树高很大可以考虑用栈或队列改成迭代写法”这样既展示了基础能力又体现工程意识。4. 常见错误与调试技巧4.1 中序遍历翻转导致重复翻转这个问题上面已经展开过但值得再强调一下。翻转二叉树的天然操作顺序应当是“先交换再处理子树”或者“先处理子树再交换”也就是前序或后序。中序会破坏左右子树的语义导致某些节点被处理两次某些节点没有被处理到。为了验证可以把上面中序版本的代码跑一个三层的测试树打印每次交换后的树结构肉眼就能看出部分节点被多翻了一次。调试时建议在每次交换后打印当前节点的左右子节点值对比预期。4.2 对空节点的处理递归版本里最容易犯的低级错误是交换左右节点之前没有检查root是否为空导致空指针异常。很多人写完代码信心满满一跑发现root.left, root.right root.right, root.left里root是None直接崩溃。所以递归的第一步永远是终止条件判断。另外交换前也不需要判断左右子节点是否为空因为交换空节点没有副作用。你完全可以直接交换两个None不影响结果。在迭代版本中弹出节点后也可能出现节点为空的情况。严格来说BFS 入队时只入队非空节点所以出队的节点一定非空这部分可以放心。4.3 测试用例设计与实际刷题经验建议至少准备以下几类测试用例空树root []输出应为空。单节点root [1]输出仍为[1]。经典三层满树root [4,2,7,1,3,6,9]翻转后输出[4,7,2,9,6,3,1]。不完全树root [1,2]只有左子节点翻转后应为[1,null,2]。链状树root [1,2,null,3,null,4]这种树可以暴露递归深度问题。用 LeetCode 默认的层序数组表示法比较直观但调试时更推荐写一个辅助函数把二叉树转换成层序列表或者写一个打印树形结构的函数看着更清楚。个人建议在本地刷题时准备一个简单的层序遍历输出函数方便验证翻转结果。我在实际刷这道题时踩过一个挺隐蔽的坑用递归写出正确代码后想当然地以为迭代版只是“换个容器存节点”结果写 BFS 时把交换放在了入队之后逻辑上成了入队完再交换代码长这样node queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) node.left, node.right node.right, node.left这样写其实也能通过因为入队时保存的是节点引用交换操作发生在入队之后但队列中已经存了这两个节点之后循环弹出时依然会处理它们。不过要注意如果先入队再交换那么入队的node.left和node.right是交换前的左右子树这会导致队列中两个节点的处理顺序与预期不同但只要所有非空节点最终都被弹出并交换一次结果依然正确。只是从逻辑清晰度来看还是先交换再入队更好因为入队的子节点正是交换后需要继续处理的子树。5. 从 Hot 100 看这道题的意义5.1 为什么翻转二叉树能进 Hot 100Hot 100 是 LeetCode 上被刷得最多、覆盖面最广的 100 道题其中简单题不多但翻转二叉树是少数几道“看起来很简单但蕴含重要思想”的题。它表面上是考察二叉树的遍历实际上考察的是递归思维的熟练度。能不能在十分钟内写出递归版能不能解释清楚为什么中序会出错能不能顺手写出迭代版这些都能反映一个人的基础是否扎实。面试官可以用这一道题快速筛掉对二叉树遍历掌握不牢的人也可以引导候选人深入聊聊递归的栈帧变化、树的遍历框架等话题。从面试角度来说性价比极高。5.2 递归思想的迁移对称二叉树、相同的树翻转二叉树的递归框架可以迁移到很多类似题目上。比如 LeetCode 101 对称二叉树判断一棵树是否镜像对称核心也是递归比较两个节点LeetCode 100 相同的树递归比较两棵树的对应节点。这三道题可以放在一起刷。以相同的树为例核心递归逻辑是def isSameTree(p, q): if not p and not q: return True if not p or not q: return False return p.val q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)对比翻转二叉树的递归你会发现两者都是在递归处理左右子树时维护某种关系一个是“交换后返回根”一个是“比较后合并布尔值”。模板其实是一致的。5.3 实战扩展按层打印翻转后的树刷完翻转二叉树后可以自己给自己加一个需求翻转完再把结果按层打印出来。这一步能顺便复习层序遍历。def level_order(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(level) return result翻转之后调用这个函数如果输入[4,2,7,1,3,6,9]输出应当为[[4], [7, 2], [9, 6, 3, 1]]。看到这个结果对镜像翻转的理解会直观很多。我个人在实际刷题中的体会是翻转二叉树这道题代码量越小越需要在一开始就想清楚递归顺序。很多人代码背得滚瓜烂熟但换一种遍历顺序就懵了。建议刷题时不要只满足于通过而是把前序、后序、BFS、DFS 四种写法都手写一遍再自己画几棵树模拟执行过程。这样刷完后面遇到对称二叉树、路径总和、二叉树的最近公共祖先等题目时递归分析能力会有明显提升。最后再分享一个小技巧如果担心递归太深导致栈溢出可以先把递归版写出来再改成显式栈的迭代版。这种“先递归后迭代”的顺序比一上来就写迭代版更容易抓住核心逻辑。翻转二叉树作为 Hot 100 里少有的“让人越刷越清醒”的题目值得反复写几遍直到闭着眼睛都能画出递归栈的变化过程。