LeetCode HOT 100 的第 94 题“二叉树的中序遍历”可能是很多人口中“最简单的一道中等题”。题目本身真的简单到爆给定一棵二叉树返回中序遍历结果。但你要是以为这题就是写个递归3分钟交卷那你大概率错过了一整片森林。先点破核心中序遍历看似只是“左-根-右”三个字实际牵扯递归、迭代、显式栈、线索树、Morris 遍历等多套知识点不同解法在时间与空间复杂度上有明显差异而它在二叉搜索树相关的系列题目里就是地基。这篇文章我想把我刷这道题时反复迭代过的版本、踩过的坑、以及面试时被追问过的延伸问题一次讲清楚。我默认你至少有最基本的数据结构概念知道二叉树长什么样、节点有 left 和 right 两个指针、以及什么是前序/中序/后序遍历。完全零基础的同学也可以看我会从最基础的“左根右”开始讲起并且保证每个解法都给出可以直接复制的代码和本地测试方式。1. 先把中序遍历的定义和递归版写透1.1 一条很短的规则左根右中序遍历的定义就三个字左根右。具体来说对于任意一棵子树先完整遍历它的左子树再访问根节点最后完整遍历右子树。左子树内部又遵循同样的规则直到子树为空才停止。这个“递归”结构天然就嵌在定义里不是说实现的时候碰巧用了递归而是这个定义本身就是递归式。理解这个东西的关键我发现有时候不在“左根右”这三个字本身而在于“访问”这个词。很多初学者会把“访问”理解成“看一眼这个节点”或者“来到这个节点”实际上在遍历语境里“访问”严格指把节点值存入结果集的那一刻。一棵树你总会被指针指到很多次但真正被“访问”的时机才是区分遍历序的关键。中序遍历中节点被访问的时机是它的左子树已经全部处理完正要转向右子树的那个瞬间。举个例子一棵最简单的三节点二叉树根为 2左孩子为 1右孩子为 3。中序遍历的过程是先进入根节点 2发现它有左孩子 1于是先处理左子树左子节点 1 没有左孩子访问 1回到根节点 2访问 2再进入右子节点 3右子节点没有左孩子访问 3。结果就是 [1, 2, 3]。这个例子看似简单但你把它想清楚后面的迭代写法就有底了。1.2 递归实现最接近数学定义的写法递归版本是这道题最直白、最不容易写错的实现。用 Python 表达就是def inorderTraversal(root): res [] def dfs(node): if not node: return dfs(node.left) res.append(node.val) dfs(node.right) dfs(root) return res这段代码本身没有任何值得炫耀的地方但我建议你把它背到条件反射的程度因为很多相关的题都是在它基础上改一行。比如前序遍历就是把res.append(node.val)放到两个dfs调用之前后序遍历放在最后。真正值得思考的是递归到底是怎么跑起来的。每个递归调用都会在系统调用栈上压一个栈帧记录当前执行到的位置和局部变量。你dfs(root)时会先一直往左走dfs(root.left)、dfs(root.left.left)……直到某个节点没有左孩子dfs(None)直接返回然后系统栈像“回放”一样弹回上一层执行res.append(node.val)再进入右子树。这个过程就是典型的“深入到底再回头”。递归版的优点是思维负担极低几乎就是翻译定义。缺点也很明显树如果很深比如一条链状树有 1 万个节点递归会同时占用 1 万个栈帧可能直接栈溢出。我实测在本机用 Python 跑深度为 1000 的链状树就已经能感觉到递归深度限制的存在深度上万直接RecursionError。这在 LeetCode 上虽然不常见但在真实业务环境里处理超深树时就是隐患。所以我当初做这道题的时候就给自己立了一个规矩递归版本要会但迭代版本必须更能打。接下来进入显式栈模拟的部分这才是面试官想看的重点。2. 迭代实现搞懂显式栈就入门了2.1 从递归到迭代把系统栈变成自己的栈迭代写法的核心思路就是手动维护一个栈模拟递归过程中系统栈的行为。递归的每次调用就像把“任务”压进栈函数返回就像出栈。只不过系统栈替你管理了“执行到哪一步”的状态而你手写迭代时必须自己想清楚节点什么时候入栈、什么时候出栈、出栈之后做什么。我第一次写迭代中序遍历时犯过一个很低级的错误以为只要把头节点压栈然后弹出来访问再把左右孩子按某种顺序压进去就行。前序遍历确实可以这么干但中序遍历不行。因为中序遍历要求“左子树全部处理完才能访问根”如果根一入栈就出栈访问左子树完全没被处理顺序就错了。很多人在这里绕不过弯是因为把问题当成了“顺序调整”实际上问题是你必须先把整条左链处理完再回头看根。所以正确的策略是一路向左。指针不断走向左孩子并且沿途把每个节点压入栈。走到空节点时说明左链到底了这时从栈顶弹出一个节点这个节点就是当前子树里“最先可以访问”的那个因为它的左子树已经处理完了。访问它之后才转向它的右孩子继续同样的“一路向左”过程。用一句顺口溜帮自己记忆有左往左压没左就出栈出栈访问后往右转。2.2 标准迭代写法与分步拆解代码不长但每一行都值得琢磨def inorderTraversal(root): res [] stack [] cur root while cur or stack: while cur: stack.append(cur) cur cur.left cur stack.pop() res.append(cur.val) cur cur.right return res外层循环条件是cur or stack也就是两个条件有一个成立就继续还有节点要探查cur 非空或者栈里还有等待处理的节点。如果两个都空了说明整棵树遍历完成。内层循环while cur负责把当前节点和它的整条左链依次压栈。注意这里没有访问操作只有压栈。等到 cur 变为 None说明已经越过了某个叶子节点的左空指针此时弹栈。弹出栈顶元素后立即res.append(cur.val)这一步是真正的“访问”。访问完把cur cur.right。这里有个细节如果右孩子为空外层循环会继续走while cur发现 cur 是空直接跳过内层再从栈里弹下一个节点。如果右孩子非空就继续进入右子树的左链探索。我强烈建议你拿一棵稍微复杂的树手动画一下过程。试一棵根为 4、左子树是 2-1-3、右子树是 6-5-7 的满二叉树。压栈顺序是 4、2、1遇到空后弹出 1 访问然后 cur 指向 1 的右孩子空继续弹出 2 访问cur 指向 3压 3弹出访问……整个过程走一遍中序 [1,2,3,4,5,6,7] 自然就出来了。手推几次比看十遍代码都有用。2.3 颜色标记法更容易记忆的迭代版本标准迭代写法面试中已经足够但如果你被要求“能不能用迭代写得更清楚”或者你自己记不住那个“内层往左、外层弹出”的套路可以用颜色标记法兜底。它的思路是给每个节点附带一个状态白色代表“还没处理该节点的子树”灰色代表“该节点的左子树处理完了该访问本节点”。代码也支持统一改成前序或后序只要调整入栈顺序非常适合记忆def inorderTraversal(root): WHITE, GRAY 0, 1 res [] stack [(WHITE, root)] while stack: color, node stack.pop() if not node: continue if color WHITE: # 栈是后进先出所以入栈顺序反过来右、根、左 stack.append((WHITE, node.right)) stack.append((GRAY, node)) stack.append((WHITE, node.left)) else: res.append(node.val) return res这个方法好理解在哪里它不要求你手动维护 cur 指针而是把“什么时候访问节点”这个信息直接编码在颜色里。白色节点入栈时说明它的子树还没处理于是按“右、根、左”的逆序把三个任务压栈——因为栈是后进先出最后压的左任务会最先弹出。左任务是白色继续展开它的子树根节点是灰色弹出时直接访问右任务最后处理。整个过程严格对应递归时的执行顺序。颜色标记法的时间复杂度同样是 O(n)空间复杂度最坏 O(n)实际使用中比标准迭代稍慢一点因为每个节点多存储了一个颜色值。但它有个巨大优势你不需要理解“为什么 cur 要这样走”只需要记住“栈反着压”这一条规则。如果你今天状态不好或者面试官追问“换个写法”这个版本是你的安全垫。3. Morris遍历把空间压到O(1)3.1 线索二叉树的思路上面说的迭代虽然摆脱了递归的栈溢出风险但显式栈最坏情况仍需要 O(h) 的空间h 是树高。而 Morris 遍历能把额外空间降到 O(1)同时保持 O(n) 的时间复杂度。它的原理说穿了是“白嫖”树里的空指针。二叉树里有很多空指针特别是叶子节点的 left 和 right。Morris 遍历的核心思路把左子树中“最后一个被访问的节点”临时挂到当前节点上。这个“最后一个被访问的节点”在中序遍历里就是左子树的最右节点。把它的 right 指针临时指向当前节点就相当于建了一条“线索”遍历完左子树后顺着线索就能回到当前节点继续向右走。可能听起来绕我换个说法。你在逛一个迷宫一定要先走完左边的通道再回到主路。你不用死记迷宫结构只需要在左边通道的尽头留一根线另一端绑在主路入口上。等左边通道走完你扯着线就能回到主路。Morris 就是干这个的。这个思路不是凭空发明的它就是传统数据结构教材里“线索二叉树Threaded Binary Tree”的简化应用。中序线索化后空 right 指针会指向后继节点。Morris 遍历动态地建立线索、使用线索、再拆除线索整个过程不额外申请 O(n) 空间只用了两个辅助指针。3.2 Morris遍历完整实现与拆解代码是这样def inorderTraversal(root): res [] cur root while cur: if not cur.left: # 没有左子树当前节点可以直接访问 res.append(cur.val) cur cur.right else: # 找左子树的最右节点 pre cur.left while pre.right and pre.right ! cur: pre pre.right if not pre.right: # 第一次到达建立线索让 pre.right 指向 cur pre.right cur cur cur.left else: # 第二次到达说明左子树已经遍历完拆除线索 pre.right None res.append(cur.val) cur cur.right return res分情况拆解第一种情况cur.left为空。这种情况下当前节点没有左子树“左根右”里的左为空直接访问当前节点然后进入右子树即可。第二种情况cur.left非空。此时需要先处理左子树但在进入左子树之前要知道左子树处理完以后怎么回到 cur。做法是找到左子树的最右节点 pre把pre.right临时指向 cur形成线索。这里最精妙的是pre.right ! cur这个判断。因为第二次到达 cur 时cur 的左子树已经通过线索回到了 cur此时pre.right已经等于 cur。所以当pre.right为空说明第一次来建立线索当pre.right等于 cur说明是第二次来左子树已经遍历完这时访问 cur 并拆除线索。整个过程需要记住的一个重点是线索用完必须拆除把树还原成原状。我见过不少人在模拟 Morris 时发现树的结构被改了最后遍历输出正确但树已经“坏”了原因就是忘记pre.right None这一行。LeetCode 判题通常只检查返回的结果列表不改树也许不会挂但面试时如果面试官检查你的输入树是否被修改这就是一个明显的 bug。还有一个值得注意的问题while pre.right and pre.right ! cur这个循环为什么会多出一个pre.right ! cur条件因为当线索已经建立之后如果你又回到了 cur第二次到达这时再找 pre 时pre 一路向右会走到线索上。如果不加这个条件循环会连到 cur 都不停直接死循环。加了这个条件第二次到达时可以正确识别“线索已存在”从而进入 else 分支。时间复杂度上虽然找 pre 的循环看起来可能重复扫子树但每条边最多被访问两次一次是建立线索时走过去一次是拆除线索时走回去。总体仍线性 O(n)。空间上只有 cur 和 pre 两个指针O(1)。这是理论上的最优解法。如果面试时让你从“递归到迭代再到 Morris”逐步优化这个版本就是你要展示的终态。我建议你把 Morris 版好好背下来因为它不单是这一题的加分点在“二叉搜索树迭代器”“中序遍历的后继节点”等进阶题中这套“找前驱、建线索、拆线索”的思维会反复出现。4. 中序序列的价值应用与延伸4.1 二叉搜索树与中序遍历强绑定为什么要单开一章讲中序遍历的应用因为这道题本身只是一个起点真正的价值在于中序遍历结果和二叉搜索树BST之间存在一条铁律——一棵二叉树是 BST当且仅当它的中序遍历序列严格递增。这句话往深了想很多看似复杂的题目瞬间有了方向。比如“验证一棵二叉树是否为二叉搜索树”也就是 LeetCode 98。最朴素的做法就是中序遍历这个树然后检查结果列表是否严格递增。如果出现res[i] res[i1]说明不是 BST。这个办法很直白时间复杂度 O(n)空间复杂度 O(n)。纯做题没问题但面试官会追问“能不能边遍历边判断不存完整列表”这时候就可以在迭代写法的res.append(cur.val)那段改成记录前一个节点值发现当前值不大于前值就直接返回 False。这样空间降到 O(h)。再比如“找出二叉搜索树中第 K 小的元素”LeetCode 230。二叉搜索树的性质决定了中序序列就是从小到大排列那么第 K 小就是中序遍历中的第 K 个节点。用迭代写法每次访问一个节点计数一次数到 K 就返回根本不需要遍历完整棵树。我当初刷这道题的时候就觉得“中序遍历是所有 BST 题目的万能钥匙”这个评价毫不夸张。类似的延伸还有求 BST 中两个节点的最近公共祖先、BST 转双向链表、恢复一棵被交换了两个节点的 BSTLeetCode 99。恢复 BST 那道题尤其经典核心做法就是中序遍历整棵树找到两个“逆序对”的位置再交换回正确节点的值。思路和中序遍历强相关。4.2 表达式树与其它应用跳出 BST中序遍历在表达式树里也有一席之地。表达式树是一种二叉树叶子节点是操作数内部节点是运算符前序遍历得到前缀表达式中序遍历得到中缀表达式后序遍历得到后缀表达式。你在编译器设计或者计算器实现里遇到表达式解析时常会用到这层关系。不过这里有个坑中序遍历表达式树得到的中缀表达式不一定带括号。你遍历 1 2 * 3 时中序结果是 1 2 3 × 对应的中缀书写会变成 1 2 * 3这碰巧没问题但如果是 (1 2) * 3中序得到 1 2 * 3含义就变了。所以真正要在中序输出里加括号需要判断运算符优先级而不是拿到中序结果直接用。这个话题可以作为延伸了解但不要在中序遍历这道题里过度纠结。另一个应用是“普适的表达式求值算法”。在部分解释器、计算器项目里会先把中缀表达式转成后缀表达式逆波兰式再通过栈求值而表达式树到后缀表达式的转化本质就是后序遍历。所以理解三种遍历之间的差异是从数据结构通往实际工程问题的基本功。某种意义上中序遍历就像是树的“按某种规则排序”的入口。无论你是做数据库索引B 树叶子之间有链式连接其实也类似线索化的行为、做 JSON 解析里的递归下降还是做 AST 的结构分析遍历树的底层逻辑无处不在。这也是为什么 LeetCode 把 94 题放在 HOT 100 里的原因——它是一道“工具题”自身简单但后面几十道中等题都拿它当垫脚石。5. 常见问题与调试实录5.1 踩过的坑与排查方法我刷这道题时踩过不少坑也见过身边同事面试时在这里翻车。整理成表格方便你排查问题。症状可能原因解决方法输出结果是前序而不是中序在进入左子树前就res.append了节点值把访问操作放到左子树处理完、弹栈之后死循环迭代版本里没有正确移动 cur或 cur 一直停在某个节点检查访问后是否执行了cur cur.right输出重复或漏输出出栈时机不对或者弹栈后没有跳到右子树确定每个节点只被访问一次注意res.append位置递归版本栈溢出树的深度过大换用迭代栈版本或 Morris 版本结果顺序正确但原树被改了Morris 遍历中线索没拆干净确认pre.right None在第二次到达时执行空树返回 None返回类型处理不当确保空树返回[]而不是 None其中最容易让人困惑的是我在颜色标记法里提到的一个细节栈的顺序是逆着遍历顺序压的。中序需要先处理左、再访问根、最后处理右压栈顺序就是先压右、再压根、最后压左。每次写错都是因为把压栈顺序和输出顺序搞混。我在本地调试时常用一个构造二叉树的小工具把 LeetCode 风格的数组输入快速转成树节点结构省得手写节点。做法是def build_tree(values): if not values: return None root TreeNode(values[0]) queue [root] i 1 while i len(values): node queue.pop(0) if values[i] is not None: node.left TreeNode(values[i]) queue.append(node.left) i 1 if i len(values) and values[i] is not None: node.right TreeNode(values[i]) queue.append(node.right) i 1 return root注意 LeetCode 的输入数组中空节点用null表示在 Python 本地测试时建议用None。这个工具我几乎在二叉树相关题里每次都用属于高频自用代码。另外一个实用技巧是写一个树形打印函数或者在遍历函数里加几个临时print观察 cur 指针的移动顺序。几次之后你对迭代过程的理解会远高于纯看书。5.2 本地测试与提效技巧如果你准备系统地刷 LeetCode我建议不要只在网页编辑器里写代码。本地搭一个最小的测试环境效率会高很多。把TreeNode定义、从前序/层序数组建树的函数、遍历函数、断言函数放在一个文件里每道二叉树题都能复用。一个简单的测试断言def test_inorder(): root build_tree([1, None, 2, None, None, 3]) assert inorderTraversal(root) [1, 3, 2] assert inorderTraversal_recursive(root) [1, 3, 2] test_inorder()你还可以批量跑一组用例空树[]-[]单节点[1]-[1]完全二叉树[1,2,3,4,5,6,7]-[4,2,5,1,6,3,7]左偏树[1,2,None,3,None]-[3,2,1]右偏树[1,None,2,None,3]-[1,2,3]这些用例覆盖了树的基本形态能快速发现“访问时机”和“遍历方向”的问题。LeetCode 的判题样例一般不会太刁钻但你自己测试时主动覆盖极端情况才是刷题效率高的原因。另外一个小技巧在本地跑复杂度过高的用例观察耗时。比如一棵 10 万节点的树递归版本和 Morris 版本的差异会非常明显这样你对“为什么需要优化空间”有直观感受。我曾经拿随机生成的 5 万节点二叉树跑过三种实现递归版本在我机器上偶尔触发递归深度限制迭代版本稳定完成Morris 版本最稳但代码出错时也最难调。读懂每种解法的适用边界比背下某一种写法重要得多。我个人的实际体会是这题第一遍刷的时候递归写一遍、迭代写一遍、Morris 写一遍看起来耗时但后面刷 BST 系列时收益巨大。最后再分享一个小技巧面试里如果被问到“中序遍历的迭代实现”你可以在写完标准迭代后补一句“如果要求空间 O(1)可以用 Morris 遍历通过线索临时改变树结构”。这句话基本能让面试官对你另眼相看因为大多数候选人只会背递归和迭代两个版本。