反转二叉树：从递归到迭代的完整拆解与运行时错误排查

1. 反转二叉树怎么就成为面试名场面了如果你常在技术社区闲逛大概率见过这个段子Homebrew 的创始人 Max Howell 去 Google 面试面试官让他写一道反转二叉树Invert Binary TreeMax 没写出来然后就被拒了。事后他发推吐槽这事程序员的反应空前一致——原来大佬也有被算法题卡住的时候。这个名场面直接让反转二叉树从一个普通的 LeetCode 简单题变成了算法圈自带梗的传说级题目。但话说回来反转这个词在技术领域其实是多义词搞 PLC 的会想到星三角降压启动的正反转控制做家电维修的会想到直流电机继电器正反转写后台的会想到 Spring 的控制反转和 C# 的依赖反转。而在算法面试里绝大多数时候它指的就是二叉树镜像——把每个节点的左右子树交换位置。这道题的定位很有意思LeetCode 上是第 226 题难度标记是 Easy。可它既让大佬翻过车又让无数初学者在运行时错误里挣扎。我的看法是它简单是因为解法短得能塞进一张名片它不简单是因为题目背后牵扯到递归理解、调用栈、遍历顺序、边界处理一大堆东西。或者说它是一个用 Easy 外壳包装的递归与遍历综合测试题。这篇内容主要面向几类人正在刷题准备面试的求职者教过学生但总被同一个问题问到的算法导师还有那些写递归总是似懂非懂、一调运行就崩的初学者。我会把这道题从递归到迭代、从正确性验证到运行时错误排查完整拆开不光是给一份能跑的代码而是把里边的原理和坑都讲清楚。2. 递归反转先理解调用栈再理解那三行代码2.1 前置知识与递归基先说最基本的数据结构定义。一个二叉树的节点通常由三部分组成节点的值 val、指向左子树的指针 left、指向右子树的指针 right。用 Python 写就是这样class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right反转二叉树的定义非常直观对于树中的每一个节点交换它的左孩子和右孩子。注意是每一个节点不是只交换根节点的两个子树。这个细节是新手上路最容易漏的——只做了一次 swap然后发现树只歪了一下头内部根本没镜像。标准的递归实现有好几种等价的写法我个人最推荐下面这种它看起来最数据结构课本def invertTree(root: TreeNode) - TreeNode: if root is None: return None root.left, root.right invertTree(root.right), invertTree(root.left) return root这段代码的秘密藏在赋值顺序里Python 会先计算等号右边的两个值也就是先递归调用 invertTree(root.right) 和 invertTree(root.left)得到两棵已经反转完毕的子树再整体交换挂到 root 上。这实际上是一种后序策略——先解决左右子树最后处理根节点。很多教材会换一种写法先交换、再递归def invertTree(root: TreeNode) - TreeNode: if root is None: return None root.left, root.right root.right, root.left invertTree(root.left) invertTree(root.right) return root这种是先交换再深入属于前序策略。两种写法最终效果一模一样区别只是交换动作发生在递归之前还是之后。理解两种姿势的存在很有用因为后文要讲的一种错误中序写法恰好是弄错了这个时机。2.2 递归执行过程推演手动模拟一次调用栈光背代码不踏实我们来手动走一遍。假设输入树长这样4 / \ 2 7 / \ / \ 1 3 6 9调用 invertTree(4)。先计算 invertTree(7)7 有左右孩子先计算 invertTree(9) 返回 9再计算 invertTree(6) 返回 6然后交换7 变成左 9 右 6。再计算 invertTree(2)同理2 变成左 3 右 1。最后把 2 和 7 交换4 变成左 7 右 2。结果4 / \ 7 2 / \ / \ 9 6 3 1看到没每一层递归返回的都是已经反转好的子树根节点最后做交换。整个过程实际上和二叉树的后续遍历完全同构——你只不过把打印节点这个动作换成了交换左右孩子。为什么递归能行因为反转问题具有天然的自相似性一棵树的反转等于先反转左子树、再反转右子树、最后把两边对调。子树的反转又是一个同样的问题只是规模更小。终止条件就是到达空节点什么都不做返回空。理解调用栈是掌握递归的关键。每次递归调用都会在系统栈里压一个新的栈帧包含了这次调用的参数和局部状态。对于扭曲成一条直线的斜树递归深度等于节点数量。树有 10000 个节点递归调用就要压 10000 层栈帧栈空间耗尽就直接RecursionError或者StackOverflowError。这也是很多人写二叉树程序总在运行时出错的深层原因之一后面专门说。2.3 中序递归的隐蔽陷阱一个看似合理但结果错误的版本接下来是这个主题里我最想写的一个坑。很多人学完前序、中序、后序遍历之后会觉得反转二叉树用哪种遍历顺序都无所谓。前序的代码是交换-递归左-递归右后序的代码是递归左-递归右-交换那中序的代码是不是写成递归左-交换-递归右就行了答案是否定的。看这个看起来完全合理的中序实现def invertTree_wrong(root: TreeNode) - TreeNode: if root is None: return None invertTree_wrong(root.left) # 先处理左子树 root.left, root.right root.right, root.left # 交换左右孩子 invertTree_wrong(root.right) # 再处理右子树 return root我们还是用上面那棵树来推演。第一步处理节点 4递归处理 4 的左子树 2。处理 2 的过程中递归处理 1无孩子返回。交换 2 的左1和右32 变成左 3 右 1。再递归处理 2 的右子树此时右子树是 1无孩子返回。回到 4交换 4 的左2和右74 变成左 7 右 2。再递归处理 4 的右子树此时右子树是 2。而 2 之前已经被反转过一次内部是左 3 右 1。递归处理 2 的左子树 3无孩子返回。交换 2 的左右2 变回左 1 右 3。递归处理 2 的右子树 3无孩子返回。最终这棵树变成了4 / \ 7 2 / \ / \ 6 9 1 3问题很明显原右子树 7 被换到左边后内部完全没有被递归反转6 和 9 没交换而原左子树 2 因为位置变化被中序逻辑处理了两遍等于反转了两次又变回原样。为什么中序会出问题因为中序的顺序是左根右交换操作位于中间它会把尚未反转的右子树换到左边但递归流程接下来却去处理了已经反转过的左子树右侧新位置上的子树反而成了漏网之鱼。这个坑在网上讨论热度很高面试时如果你能主动讲出中序递归不行原因是交换之后左右子树身份变化递归路径和子树身份错位面试官一般会眼睛一亮。它也是区分真懂递归和背模板的好问题。2.4 递归版本的复杂度与局限递归反转的时间复杂度是 O(n)每个节点都被访问常数次。空间复杂度取决于系统调用栈深度也就是树的高度 h。对一棵平衡树h 是 O(log n)对一棵极度倾斜的树h 逼近 n递归版本随时可能爆栈。所以面试里如果追问递归有什么问题标准回答思路是空间开销受树高影响最坏情况下 O(n)而且系统栈的容量是有限且不可控的生产环境处理大深度树时存在风险。要突破这个局限就得用显式的栈或队列做迭代。这不是面试官故意刁难而是真实工程里确实会遇到的约束。3. 迭代反转用队列和显式栈替代系统递归3.1 层序法用一个队列手动完成逐层反转如果不想依赖系统栈最直观的迭代写法是用队列做层序遍历。思想很简单从根节点开始每弹出一个节点就交换它的左右孩子再把非空的孩子重新入队直到队列为空。from collections import deque def invertTree_bfs(root: TreeNode) - TreeNode: 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来手动走一下最开始的例子。初始队列[4]弹出 4交换左右孩子4 变为左 7 右 2入队 7 和 2。队列[7, 2]。弹出 7交换左右孩子7 变为左 9 右 6入队 9 和 6。队列[2, 9, 6]。弹出 2交换左右孩子2 变为左 3 右 1入队 3 和 1。队列[9, 6, 3, 1]。后面弹出的 9、6、3、1 都没有孩子只交换空指针然后直接跳过。整个过程等价于层序遍历只是把访问节点换成了交换孩子。这种写法最大的优点是空间可控且好理解空间复杂度是 O(w)其中 w 是树的最大宽度最坏情况下比如完全二叉树的最后一层w 约等于 n/2也是 O(n) 量级但不会遇到系统栈深度崩溃的问题。这里有一个容易犯的错交换完左右孩子之后必须先判断左孩子是否为空再入队不要把空节点塞进队列。如果直接把None放进去弹出后访问node.left就会抛空引用异常。这也是写二叉树程序为什么总是报运行时错误的高频来源之一。3.2 前序法用栈模拟调试器里的调用栈另一种迭代写法是显式栈模拟的是递归版本的系统调用过程。核心逻辑是从栈里弹出一个节点交换它的左右孩子然后把左右孩子按顺序压栈。由于栈是后进先出如果你想前序遍历的顺序是根-左-右就先压右孩子再压左孩子。def invertTree_stack(root: TreeNode) - TreeNode: 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这个版本和层序法的代码几乎长得一模一样只差两点层序法用deque.popleft()从头取节点栈版本用list.pop()从尾部取节点入队的顺序略有不同。但两者处理结果完全一样因为反转操作的局部性很强——每个节点的交换不依赖兄弟节点被处理的先后顺序所以只要保证每个节点恰好被访问一次用什么遍历顺序都能成功。空间复杂度方面栈版本是 O(h)和最坏情况下的树高一致。对斜树来说 h 等于 n所以最坏空间复杂度同样是 O(n)但栈是分配在堆上的显式数据结构容量比系统栈宽裕得多不容易触发栈溢出。3.3 两种迭代选择与一道趣味追问层序法和栈法该怎么选我的建议是优先记住层序版因为它的逻辑最贴近二叉树镜像的直观定义也更容易向别人讲清楚。栈版本作为递归的替代方案适合你在面试里被追问能不能不用递归也不爆栈时拿出来。如果面试官继续加码问你可不可以只用一个变量实现那是想听 Morris 遍历的思路。反转二叉树用 Morris 并不优雅因为 Morris 遍历的核心是用线索来节省栈空间你反转树的过程中必须大规模修改指针指向维护线索的成本畸高。这里的结论是反转二叉树老老实实用 BFS 或显式 DFS 就好线索化遍历在本题反而复杂化可以作为一个讨论点提出来显得你不是背答案的人。还有一个经常被拿来当延伸题的问题如果输入是一棵二叉搜索树BST反转后还是 BST 吗答案是——如果按照左小右大的标准定义反转后左子树全比根大、右子树全比根小不满足传统 BST 性质。它是一棵严格反向的 BST。如果把比较规则也镜像翻转那它的确是合法的镜像 BST。这属于题外话但能体现对搜索二叉树性质的掌握。4. 反转结果的验证确保你没写出看似正确实则跑偏的代码4.1 构造 LeetCode 风格的测试数据很多初学者把代码写完、样例一跑就宣布完工这不行。写树相关的程序最关键的是具备构造测试用例和可视化的能力。LeetCode 给的是层序数组比如[4,2,7,1,3,6,9]我们需要把它转换成链式二叉树来测。用层序数组建树的逻辑是数组的第一个元素是根之后每两个元素依次作为当前层节点的左右孩子。注意这里要用None表示空位。下面给一个常用的辅助函数def build_tree(level_order: list): if not level_order or level_order[0] is None: return None root TreeNode(level_order[0]) queue deque([root]) idx 1 while idx len(level_order): node queue.popleft() if idx len(level_order) and level_order[idx] is not None: node.left TreeNode(level_order[idx]) queue.append(node.left) idx 1 if idx len(level_order) and level_order[idx] is not None: node.right TreeNode(level_order[idx]) queue.append(node.right) idx 1 return root这个函数的常见 bug 是索引越界和 None 节点没有正确跳过。注意我每次都会先检查idx len(level_order)再访问数组。很多写着写着就运行时错误的树代码问题就出在这里数组越界或者对一个None节点调left。建好树之后还需要一个把树转回层序数组的打印函数便于肉眼比对def tree_to_level_order(root: TreeNode): if root is None: return [] result [] queue deque([root]) while queue: node queue.popleft() if node is not None: result.append(node.val) queue.append(node.left) queue.append(node.right) else: result.append(None) while result and result[-1] is None: result.pop() return result最后一位的连续None会被去掉这是为了对齐 LeetCode 的输出习惯。4.2 两种高性价比的自测方案第一种直接比层序结果。输入[4,2,7,1,3,6,9]反转后期望输出[4,7,2,9,6,3,1]。这个比对只能证明样例过了不够充分。第二种利用镜像树的前序遍历等于原树后序遍历逆序这个性质。这是一个冷门但好用的关系手动验证一下。原树前序遍历是[4, 2, 1, 3, 7, 6, 9]后序遍历是[1, 3, 2, 6, 9, 7, 4]把后序遍历倒过来得到[4, 7, 9, 6, 2, 3, 1]。反转树的前序遍历恰好就是[4, 7, 9, 6, 2, 3, 1]。把它写进测试代码里等于对整棵树的结构做了一个强校验比只比对层序输出可靠得多毕竟层序输出丢失了部分层级信息。第三种是最朴素的验证对反转结果再反转一次如果得到的树和原树层序一致说明第一次反转基本没写错。这个性质依赖反转操作的幂等性——确切地说是互为逆运算连续做两次镜像应该还原出原来的树。4.3 边界输入自测清单做树相关的题养成条件反射式地测一批边界用例空树[]反转后应该返回None而不是抛异常。单节点[5]反转后还是[5]。只有左子树的斜树[1, 2, None, 3, None, ...]反转后变成只有右子树的斜树。深度特别大的树比如 10000 层斜树递归版本直接爆栈迭代版本应该还能正常返回。节点值出现负数或者0别把None和0搞混这是树测试里特别容易踩的坑。这些用例挨个跑一遍如果全部通过再提交 LeetCode 也好应对面试自测也好基本才算合格。5. 写二叉树程序时为什么总是报运行时错误一份排查清单5.1 最常见的空指针根因、表现与修复二叉树程序里的运行时错误第一大类就是空引用。报错信息在各语言里不一样Java 是NullPointerExceptionC 是 segmentation faultPython 里是AttributeError: NoneType object has no attribute left。不管报什么根源几乎都是同一个访问了不存在的子节点。出错场景有两种常见姿势。第一种是递归基写错。比如有人会写出这样的代码if root.left is None and root.right is None: return root看起来没错但如果某个节点只有一个孩子那么递归调用时就会传入None并在下一次判断root.left时直接爆。正确处理是进函数先判断if root is None: return None而不是判断具体哪一边为空。第二种是迭代版本里把空节点放进了栈或队列。上面层序法已经强调过入队前必须判断孩子是否为空。栈版本同理。很多初学者会觉得少判一个空关系不大实际上一棵非满二叉树里有大量空位迟早会在下一轮循环里撞上。排查这类问题的通用技巧是在访问node.left或node.right之前先反问一句这个 node 有没有可能为 None然后跟踪它入栈入队的路径。用 Python 的pdb把代码停到报错行打印一下node的值立刻就能看清楚。5.2 栈溢出递归深度与树高的关系第二大运行时错误是递归深度超限。Python 里表现是RecursionError: maximum recursion depth exceededJava 里是StackOverflowError。这不是算法思路错误而是递归实现受了系统栈限制。一个 1000 层的递归就可能逼近 Python 默认递归上限通常在 1000 左右斜树的反转必然踩线。这也解释了为什么面试题里常问递归转迭代——不是递归本身错而是它在大深度场景下不可靠。排查方式和修复方案都明确先确认树确实很深打印最大深度然后把递归改成显式栈或队列的迭代版本。对反转二叉树这种节点处理不依赖访问顺序的题目迭代改写几乎不会引入额外复杂度。顺带说一句有些同学试图调高递归上限来解决问题比如sys.setrecursionlimit(100000)。这在本地开发里可以应急但在线上环境和答题平台都是不合适的治标不治本。5.3 树显示的辅助函数让自己看见错误排查树的运行时错误光靠打印一行node.val往往不够。我强烈建议你维护一套小工具数组转树、树转层序数组、树转可打印缩进字符串。十分钟写出来后面所有二叉树题都受益。缩进打印的朴素实现长这样def print_tree(root: TreeNode, indent: str , is_left: bool True): if root is None: return print(indent (L: if is_left else R: ) str(root.val)) print_tree(root.left, indent , True) print_tree(root.right, indent , False)报错的时候把当前树打印出来对照手推例子基本一眼就能定位是哪个分支的逻辑错。很多运行时错误的真实来源是逻辑跑偏但结果还能运行这类错误最难查可视化工具是救命的。5.4 面试追问与这道题的进阶面貌最后说几个面试延伸点都是我实际交流中遇到的。反转二叉树是原地修改还是返回新树原题默认原地修改并返回根节点。如果面试官要求不改原树你需要创建一个新的节点并递归构建镜像树。后文这套复杂度分析依然适用但要注意不能直接复用原有节点引用否则改了一个另一个也会变。能不能不用递归能。三种方案本文都有层序队列、显式栈、后序递归。说到栈版本时顺便提一句空间复杂度受树高影响就显得很稳。反转和遍历顺序有什么关系这是最有深度的一个延伸。前序、后序、层序都能做唯独中序不能简单套用原因看过第 2.3 节应该都懂了。这个问题很少人答得上来答出来就是加分项。还有一个容易被忽略的小点在 Python 里交换指针用元组赋值a, b b, a非常安全但在别的语言里写成a.left a.right; a.right a.left就会出现把左子树覆盖掉的问题。你需要一个临时变量保存原值。C 里用std::swap(node-left, node-right)一行搞定Java 里就得老老实实开一个TreeNode tmp。这属于跨语言时特别容易踩的细节。对这道题本身的能力收获我个人体会是它看起来简单却能一次覆盖递归、迭代、遍历顺序、边界处理、运行时错误排查这五座大山。与其刷一百道同质化的 Easy 题不如把这一道吃透把调用栈画一遍、把中序陷阱推演一遍、把迭代版改成三遍比什么都有用。至少我自己在真正手推完它的中序错误版本之后对递归什么时候能用、什么时候不能用这件事的理解上了一个台阶。