是小鬏鬏啊如果让我挑一道最容易被低估的算法题，我大概率会选 LeetCode HOT 100 里的第 94 题：二叉树的中序遍历。标题栏里经常被人搜成 “LeeCode” 的也多半是这一道。原题看起来人畜无害，只要学过树的人都能背出“左-根-右”三个字，但真正把这道题从递归写到迭代、再从迭代写到 Morris 遍历之后，你会发现自己其实把树类题目最核心的一整套操作都过了一遍。
这篇文章不是念题解，而是把我自己从第一次写递归、到面试被追问、再到给项目里手写二叉搜索树迭代器这段经历里踩过的坑和提炼出来的方法，全部串在 94 题这一条主线上。适合刚刷完基础语法、正打算集中攻树的读者，也适合那些递归写得溜、但一让手写迭代就卡壳的同学。看完之后你会发现，中序遍历这道题的价值远不止输出一个数组那么简单。
1. 先搞清楚：中序遍历到底在“遍历”什么
1.1 一棵树被访问三次
很多初学者把遍历理解为“把节点打出来”，这其实是最大的误区。访问（visit）一个节点，和“打印”这个节点，在定义上是两回事。
对于二叉树来说，每个节点最多有左、右两个孩子。当你从父节点进入某个节点时，你天然有三个机会去处理它：第一次到达时、左子树处理完回来时、右子树处理完回来时。所谓前序、中序、后序，本质上是选择在哪个时机打印当前节点，仅此而已。
- 前序：到达节点立刻打印，然后进左子树，再进右子树。
- 中序：先钻进左子树，等左子树全部处理完，回到当前节点打印，再进右子树。
- 后序：左子树处理完、右子树也处理完，最后回到当前节点打印。
用大白话类比：你在快递站分拣包裹，每个包裹要贴上“从哪来”的标签。前序是进门就贴，中序是左边货架查完再贴，后序是两边货架都查完才贴。顺序不同，最终拿到的标签排列就完全不同。
1.2 为什么中序这么特殊
中序的特殊地位来自一条性质：二叉搜索树（BST）的中序遍历结果，必然是一个严格升序数组。这句话是很多面试题的地基。比如验证一棵树是不是 BST，最朴素的思路就是做一次中序遍历，检查结果数组是否单调递增。再比如求 BST 的第 K 大节点、转换成一棵累加树，这些题的解法模板全是中序遍历。
所以 94 题虽然只要求“输出中序序列”，它背后真正想让你掌握的是“按某种顺序稳定地访问整棵树”的能力。递归写出来是三行，迭代写出来是一个栈加两个循环，Morris 写出来是一个前驱指针。三种写法，复杂度从 O(n) 空间降到 O(1) 空间，全部围绕同一个动作：如何做到“先处理左，再处理自己，最后处理右”。
这里可以给出中序的严格递推定义：若根为空则空操作；否则中序遍历左子树；访问根节点；中序遍历右子树。用自然语言描述很简单，但变成代码时有坑，递归版里表现为系统栈被压得很深，迭代版里表现为“到底什么时候该弹出节点”。
需要模型API调用？ 免费领10W Token，多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 递归解法：最直白的写法为什么要防着它
2.1 三行代码与复杂度
LeetCode 94 的递归解法，任何一个刷题三个月的人都能写出来：
python复制def inorder_traversal(root):
if root is None:
return []
res = []
def dfs(node):
if node is None:
return
dfs(node.left)
res.append(node.val)
dfs(node.right)
dfs(root)
return res
或者更简洁的写法：
python复制class Solution:
def inorderTraversal(self, root):
if root is None:
return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
第二种写法虽然短，但每次递归都创建新的列表做拼接，时间和空间都在翻倍，实际运行不如第一种用一个全局 res 累计来得稳定。我见过不少人在线上平台为了秀短代码用第二种，遇到大输入直接超时的也不少见。
复杂度上，时间 O(n)，因为每个节点恰好被访问一次；空间 O(h)，h 是树高。这里有个多数人没注意的细节：递归空间的计数是“同时存活的最大栈帧数”。对一棵极度不平衡、退化到链状的树，h 等于 n，空间就会退化成 O(n)。线上测评的测试用例里通常不会给你十万层的链状树，一旦碰到，递归直接栈溢出。
2.2 递归到底在干嘛：一张看不见的系统栈
递归之所以简洁，是因为你不需要自己维护“刚才走到哪了”的状态。函数调用 dfs(node.left) 时，CPU 把当前帧压进系统栈，等左子树返回后弹出，才能继续执行下一行 res.append(node.val)。
这里最关键的一行是 res.append(node.val) 夹在两次递归调用之间。你可以把它理解成：系统帮你记住了“你的左子树已经处理完，现在轮到你打印自己了”。这种记忆能力是栈给的，没有栈就没有递归。
所以面试官问“递归的缺点是什么”，标准答案不是“慢”，而是“隐式地占用了系统栈空间，且不受你控制”。尤其在做算法题时，递归深度一高，程序直接崩给你看，你不会有一丝补救机会。这也是从“会写递归”走向“会写迭代”的根本动机。
2.3 为什么树遍历递归没法做尾递归优化
有人可能会说：编译器不是能做尾递归优化吗？注意，二叉树的递归调用是 dfs(node.left) 和 dfs(node.right) 两条递归路径，而且执行完递归调用之后还有一行 res.append(node.val) 要继续执行。这意味着当前帧的状态必须保留到递归返回之后，根本不可能复用栈帧。尾递归优化的前提是递归调用是整个函数的最后一步，树遍历不满足。
这一点在面试里属于加分细节。只要你能说清“为什么树遍历的递归不能像尾递归一样被优化成循环”，面试官基本就知道你真的懂递归，而不是只会背模板。
提示：不要一上来就嘲讽递归解法“太弱”。实际工作里，只要确定树的深度可控，递归写出来最不容易出 bug。算法题里考察迭代，目的也不是让你永远不用递归，而是让你理解“显式栈”这个工具，因为很多图的遍历、表达式求值的场景，都需要你自己控制栈。
3. 迭代解法：用显式栈模拟系统调用
3.1 左链到底怎么压
迭代中序的核心思路是：用自己维护的一个栈，替代系统栈。每次遍历，先把当前节点的整条左链压入栈，然后弹出栈顶访问节点，处理完右子树之后再重复。
直接上代码：
python复制def inorder_traversal_iter(root):
res = []
stack = []
cur = root
while cur is not None or stack:
while cur is not None:
stack.append(cur)
cur = cur.left
node = stack.pop()
res.append(node.val)
cur = node.right
return res
这段代码短短十行，但它是所有“非递归树遍历”的基础。我每次给别人讲都要画一张图：
- 从根节点出发，一路向左，路过的所有节点全部入栈。走到最左叶子时，cur 变成 None。
- 从栈里弹出一个节点，这个节点的左子树已经处理完了，所以可以打印它。
- 把 cur 指向弹出的节点的右孩子，回到第 1 步。
为什么能保证“左子树已经处理完”？因为你把整条左链都压进了栈里，并且是从底到顶的顺序。最顶上的永远是“最左的节点”，它的左孩子为空，相当于左子树处理完了；打印它之后，接着去处理它的右子树。它的右子树处理完，再弹栈，弹出的就是它的父节点，此时父节点的左子树也确保了处理完。
3.2 用一个最小例子走一遍
假设树是：
code复制 1
\
2
/
3
- 初始 cur = 1，栈空。
- 循环内层：压入 1，cur 走到 1.left = None，结束。
- 弹出 1，打印 1，cur 指向 1.right = 2。
- 内层：压入 2，cur 走到 2.left = 3。
- 内层：压入 3，cur 走到 3.left = None。
- 弹出 3，打印 3，cur 指向 3.right = None。
- 栈非空（里面有 2），继续外层；内层 cur 是 None，跳过。
- 弹出 2，打印 2，cur = None。
- 结束，结果 [1, 3, 2]。
对照中序定义：1 的左子树为空，先打印 1；然后处理右子树 2，2 的左子树里有 3，先打印 3，再打印 2。符合。
这里强调一个新手最容易踩的坑：cur = node.right 这一行，很多人写成 cur = node，结果死循环打印同一个节点。因为刚刚弹出栈的节点已经处理完了，必须转向它的右子树，而不是回到它自己。
3.3 复杂度与“最坏情况”
迭代解法时间 O(n)，每个节点入栈一次、出栈一次。空间 O(h)：极端情况下，栈里最多同时存一条“从根到最深叶子的左链”，深度就是树高 h。
同样是一棵链状树，h = n，空间仍然是 O(n)。所以“迭代”并不能把中序遍历的空间复杂度降为 O(1)，它只是把不可控的系统栈变成了可控的显式栈。真正的 O(1) 空间方案，是下一章要讲的 Morris 遍历。
这里可以多提一句：显式栈解法还有一个变体是用“双栈”做中序，本质上先做一遍“根右左”的遍历再倒序输出。个人不建议记这种变体，因为它只在后序里意义比较大，中序上用左链法是最好理解的。
4. Morris 遍历：O(1) 空间的黑魔法
4.1 核心思想：利用空右指针作为回程标记
Morris 遍历的核心思想是：中序遍历需要“先钻到最左边，再回退到父节点”，这个回退动作原本靠栈记录。Morris 的聪明之处在于，它可以借用叶子节点的空右指针，把“该回退到哪个节点”的信息直接写在树上。
具体来说，在遍历过程中，每当你准备进入当前节点 cur 的左子树之前，先去左子树里找到“最右边的节点”，这个节点是左子树中序遍历的最后一个访问节点。它的右指针若是空的，就把它指回 cur，相当于架了一座回程的桥；等整棵左子树处理完，最后通过这座桥回到 cur，再把桥拆掉（恢复为空）。
4.2 中序 Morris 的完整代码
python复制def inorder_traversal_morris(root):
res = []
cur = root
while cur is not None:
if cur.left is None:
res.append(cur.val)
cur = cur.right
else:
pre = cur.left
while pre.right is not None and pre.right is not cur:
pre = pre.right
if pre.right is None:
pre.right = cur
cur = cur.left
else:
pre.right = None
res.append(cur.val)
cur = cur.right
return res
这段代码看起来比迭代复杂很多，但逻辑可以拆成三块：
cur.left is None：当前节点没有左子树，那就直接打印当前节点，然后去处理右子树。pre.right is None：在 cur 的左子树里找到了最右节点 pre，且它的右指针为空。说明这是第一次访问 cur，还没进入左子树，于是把 pre.right 指向 cur，建立回程桥，然后 cur 往左走。pre.right is cur：说明左子树已经处理完了，桥也探测到了。此时断开桥（pre.right = None），打印 cur，然后 cur 往右走。
4.3 走一遍全过程，理解桥的建立与拆除
还是用上面那棵链状树：
code复制 1
\
2
/
3
- cur = 1，左子树为空，打印 1，cur = 2。
- cur = 2，左子树是 3，找左子树最右节点：pre = 3，pre.right 为空，于是 pre.right = 2，cur = 3。
- cur = 3，左子树为空，打印 3，cur = 3.right = 2。
- cur = 2，左子树是 3，找最右节点：pre = 3，但 pre.right 现在是 2，说明桥已经架好，左子树处理完了。断开桥：pre.right = None，打印 2，cur = 2.right = None。
- 结束，结果 [1, 3, 2]。
整个过程没有用任何额外的栈或者队列，唯一被修改的就是叶子节点 3 的右指针，而且在返回时把指针恢复了。所以遍历结束后，树的结构跟遍历之前完全一样，不会破坏原树。
注意：很多资料说 Morris 遍历“不修改原树”，严格讲是“遍历过程中临时修改，结束时恢复原状”。如果代码在中途报错或者被中断退出，树是可能保持修改状态的。我在做项目时用过一个基于 Morris 思路的迭代器，每次迭代完都要小心检查恢复，否则下一次遍历的结果就会出问题。
4.4 Morris 的两个代价
Morris 的优点是空间 O(1)，时间上平均 O(n)，但有一个隐藏常数：每次访问一个节点时，找前驱可能要走一段链。如果每次都走完，总复杂度怎么算保证 O(n)？
这里有个经典的摊还分析：每个节点作为“前驱”被寻找的次数是有限的。可以理解为，每一条边在构建桥梁和探测桥梁时最多被走两次：一次顺着走到最右节点，一次通过桥回来。所以总时间是 O(n)，但常数比递归和迭代大。实际测下来，在小数据集上 Morris 反而更慢；数据集特别大（比如几十万个节点）且空间受限时，Morris 的价值才真正显现。
这个点面试官如果会追问“Morris 不是每个节点都找前驱，复杂度到底是 O(n) 还是 O(n log n)”，你要能给出摊还分析的结论。我见过不少同学在这里翻车，背了代码却没理解为什么总代价是线性的。
5. 一个模板串起前中后序：递归转迭代的通法
5.1 标记法：给每个入栈的节点打上状态
左链法只能解决中序，如果想要一个套路同时解决前序、中序、后序的迭代版本，推荐使用“标记法”。它的思路极其简单：系统栈之所以能实现三种顺序，是因为函数调用栈里保留“执行到哪一行”的信息。我们可以给每个入栈的节点附加一个布尔状态，表示“这个节点是否已经被处理过”。
Python 里可以用 (node, visited) 二元组，visited 为 False 表示还没访问过，为 True 表示子树已经处理完，可以打印了。
中序的代码长这样：
python复制def inorder_traversal_marked(root):
res = []
stack = [(root, False)] if root else []
while stack:
node, visited = stack.pop()
if node is None:
continue
if visited:
res.append(node.val)
else:
stack.append((node.right, False))
stack.append((node, True))
stack.append((node.left, False))
return res
注意入栈顺序是“右、中、左”。栈是后进先出，我们希望先处理左、再中、再右，所以压栈顺序要反过来：先把右压进去，再压标记为 True 的当前节点，最后压左。
想写前序，只需要改变压栈顺序：压右、压左、压当前（标记为 True），这样出栈顺序就是“中、左、右”。写后序则压中（标记 True）、压右、压左，出栈就是“左、右、中”。
这个方法比左链法好记好推广，缺点是每个节点要额外出入栈一次。面试时如果题目只让写中序，我一般直接上左链法；如果题目要求写出三种遍历的统一迭代模板，我就会写这个标记法。
5.2 为什么系统栈能做到的事，显式栈都能做到
标记法的本质，是把“递归函数执行到哪一行”这个信息显式地记录进栈。任何递归程序，理论上都可以通过类似的方式转成迭代。这句话听起来像理论课，实际写代码时很有指导意义：当你不知道怎么把一个递归转成迭代时，就去想“系统在递归里多做了哪件事”，然后把这件事用变量或者标记模拟出来。
我踩过的一个坑是，最初记标记法时把 stack.append((node, True)) 放在 stack.append((node.right, False)) 之前，结果打印顺序完全拧了。后来总结出一个口诀：入栈顺序是打印顺序的逆序。你要中序打印“左中右”，入栈就得先右、再中、再左。只要抓住这个口诀，前中后序三种遍历的标记法代码可以一分钟之内默写出来。
这个模板还有一个额外的好处：它可以处理一些特殊的题目，比如“在遍历中间某个条件满足时就停止”，因为你有完全的控制权，不需要等整个递归调用栈自然退出。这在做成绩合格判断、表达式短路求值这类场景里特别实用。
6. 中序遍历在真实场景里的应用：不止是刷题
6.1 二叉搜索树的升序输出
最直接的应用是 BST 排序。给一棵二叉搜索树，中序遍历就能得到一个有序数组。很多人知道这一点，但实际项目中没有人为了排序刻意构造一棵 BST——直接排序更快。BST 中序遍历真正有价值的地方，是在“数据频繁插入删除 + 需要动态维护有序序列”的场景。
举个典型例子：你要维护一个排行榜，动态插入新成绩，随时要拿到“第 K 名”的成绩。如果用数组，每次插入都是 O(n)；如果用 BST + 中序遍历，每次插入 O(log n)，中序遍历一次 O(n)。当需要频繁第 K 查询时，配合子树节点计数，甚至可以在 O(log n) 时间直接定位第 K 个，这就是“二叉搜索树 + 中序思想”的威力。
6.2 表达式树的还原
编译器在处理算术表达式时，经常会把表达式解析成一棵表达式树：叶子节点是数字，非叶子节点是操作符。对这棵树做中序遍历，就能得到我们平时写的中缀表达式，比如 (1 + 2) * 3。
不过有个细节要提醒：单纯用中序遍历打印出来的表达式，没有括号，会导致运算顺序出问题。比如“左操作数是加法”时，需要额外加括号。这个例子很好地说明，中序遍历输出的是一个“序列”，后面要怎么解释这个序列，还得结合具体语义。我在做某个模拟计算器项目时，就是先构造表达式树，再做中序遍历生成人类可读的表达式，遇到低优先级节点加括号，这个处理逻辑花了整整一个下午调试。
6.3 数据库索引里的升序链表
现代数据库的索引大量使用 B+ 树。B+ 树的叶子节点之间用指针串联，直接形成一个有序链表，本质上就是一种“中序顺序”的物化。在做范围查询（range scan）时，数据库只需要沿着叶子节点链表从左到右扫描即可，不需要反复回溯树结构。虽然 B+ 树不是二叉树，但它把“中序遍历得到的顺序”预先存储在叶子指针里，这个设计思想与二叉树中序遍历如出一辙。
所以，别觉得中序遍历只是考试玩具。你在业务系统里做“按时间戳排序的最近记录查询”，底层索引用到的就是类似逻辑。理解中序，等于理解了数据库索引为什么要搞成树形结构而不是链形结构。
6.4 面试必考：二叉搜索树迭代器
很多大厂的面试题要求实现 next() 返回 BST 中下一个最小节点，hasNext() 判断是否还有下一个。标准解法就是“用栈模拟中序遍历的迭代器”。
python复制class BSTIterator:
def __init__(self, root):
self.stack = []
cur = root
while cur:
self.stack.append(cur)
cur = cur.left
def next(self):
node = self.stack.pop()
if node.right:
cur = node.right
while cur:
self.stack.append(cur)
cur = cur.left
return node.val
def hasNext(self):
return len(self.stack) > 0
这个迭代器就是上面左链法代码的封装版。next() 每次弹出栈顶节点前，先把它右子树的整条左链压栈，保证下一次弹出的仍然是“全局最小未访问节点”。理解了这个迭代器，你就能把“树”当成“有序集合”来用，很多二叉搜索树上的问题都能转化成扫描问题。
7. 刷题与面试中的避坑清单
7.1 边界条件永远先测这四个
我把中序遍历相关的边界条件归纳成四类，写代码前先把这四种树都过一遍：
- 空树：root 为 None，正确输出 []。
- 单节点树：正确输出单个值。
- 只有左子树的链状树：左链法是否会在 while cur 循环里压入所有节点，输出顺序是否升序。
- 只有右子树的链状树：每次只压一个节点，马上弹出，注意
cur = node.right的赋值是否写在打印之后。
大部分迭代写错的案例，都是因为这四种树里的某一种导致死循环或者漏节点。我当时排查一个“只有右子树却打印出 [根, 左子树...]”的 bug，查了半小时才发现是 cur = node.right 写到了 res.append(node.val) 之前，访问顺序被提前弄乱。
7.2 面试时怎么把这题答成一个系统性的展示
这道题是高频 HOT 100，很多面试官会觉得“太简单”，所以真正考察的其实是你的系统性和深度。我建议的答题递进层次是：
- 先说定义：中序是左-根-右，BST 升序。
- 写递归，说清“系统栈”和复杂度 O(n) 时间、O(h) 空间。
- 面试官追问“不用递归会怎样”，立刻切换迭代写法，解释显式栈如何等价于系统栈。
- 若面试官继续追问“能不能 O(1) 空间”，再写 Morris 遍历，重点讲“前驱节点的桥”这个思想和恢复原树的过程。
- 最后补一句：如果只是中序，左链法最直观；如果三种顺序都想统一，用标记法。
按照这个顺序，从递归到 Morris 就是一条完整的知识链。一个面试官如果只准备让你背 94 题的答案，听到你能主动展开到“Morris 为什么是线性摊还复杂度”，基本会有意外之喜。
7.3 写代码时的三个卫生习惯
- 入栈前先判空，不要让 None 入栈再去判断，这样逻辑更清爽。
- 更新指针时用新变量承接，别复用 cur 顺手改值却忘了下一步逻辑。
- 每写完一版，先手动跑一棵三节点树，确认输出顺序。
这三个习惯看起来琐碎，但在笔试场景帮了我大忙。有一次在线笔试时间紧张，我写完迭代版直接提交，用三节点树手算了一遍才想起左子树为空时要特殊处理，临时补上。没有这个习惯的话，那一题大概率挂。
我自己刷 94 题的时候，前前后后改了三版代码，从递归到左链迭代，再到把 Morris 写对整整花了一晚上。后来发现，这道题就像树这个章节的“缩略图”：你把它吃透，前序后序、二叉树迭代器、BST 相关题目基本都能顺下去。实际工程里用到中序的地方不算多，但“用栈模拟递归”“用空指针做状态标记”这两个思路，在写解析器、遍历 JSON 嵌套对象、处理 AST 时，都是同一套底层逻辑。
最后分享一个小技巧：如果今天只是应付笔试，迭代法必须背熟，Morris 知道原理即可；如果目标是面试表现，建议你亲手把 Morris 遍历的全过程，对照一棵 5 个节点的树，在纸上走三遍。走完三遍，你就不只是“记得代码”，而是真的理解它为什么对了。这道题我至今看到还是会觉得有意思，希望我的经验能帮你少走一点弯路。