题目描述
思路解析
一句话答案：LeetCode 94 二叉树的中序遍历口诀是「左根右」：递归版三行写完；面试更常追问的迭代版用显式栈——从当前节点一路向左把沿途节点压栈，弹出栈顶即访问，再转向它的右子树重复。每个节点恰好入栈、出栈各一次，时间 O(n)，空间 O(H)，H 为树高。
中序遍历的顺序到底是什么
中序遍历要求对每个节点都遵守同一条规则：左子树全部访问完，才轮到根，最后才是右子树。「中」指的是根被夹在中间输出。这个定义是递归的——访问左子树时，内部同样按左根右展开。由此能直接推出一个结论：整棵树第一个被访问的节点，一定是从根一路沿左孩子走到底的那个最左下节点；最后一个则是最右下节点。
递归写法为什么天然正确
递归版几乎是定义的直译：先调用 inorder(root.left)，再收集 root.val，最后调用 inorder(root.right)。「左子树必须先处理完」这条约束不需要任何额外代码来保证——函数调用栈替你保证了：inorder(root.left) 不返回，后面两行根本不会执行。思路上递归是最清晰的版本，但面试常追问「不用递归怎么写」，所以显式栈的迭代版才是本题的重点。
迭代版为什么要一路向左压栈
不用递归，就得自己接管调用栈的职责，这正是显式栈的作用。从当前节点出发一路向左，把沿途节点依次压栈：栈里存的是「左子树还没处理完、暂时不能访问」的节点，同时也是之后往回走的路。走到最左尽头时，栈顶恰好是所有未访问节点中最靠左的那个——它没有左孩子或左子树已清空，按左根右的规则，此刻正该轮到它。
弹出即访问，凭什么成立
整个迭代过程维持一条不变量：任何节点被弹出时，它的左子树必然已经全部访问完。原因很直接——节点入栈之后，算法先钻进它的左子树，左边全部处理完毕才可能弹到它。所以弹出即可放心访问，访问完把指针转向右子树，对右子树再重复「一路向左压栈」。循环条件写成栈非空或当前指针非空，两者都空才说明整棵树走完。
复杂度与常见的翻车点
时间 O(n)：每个节点恰好入栈一次、出栈一次，n 为节点数。空间 O(H)：栈里最多同时存一条从根到当前位置的左链，H 为树高，链状树最坏 O(n)。两个高频错误：把顺序写成根左右，那是前序遍历，结果整体错位；迭代时压栈方向搞反，弹出的就不再是当前最左的未访问节点。若被追问 O(1) 空间的做法，可以提 Morris 中序遍历：借叶子的空右指针临时指回后继节点，遍历完再拆掉线索，时间仍 O(n)，空间降到 O(1)，属进阶考点。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心一句话：中序 = 左根右。左子树全访问完才轮到根，再右子树。
完整的二叉树。中序遍历从根开始，一路沿左孩子向下走到最左下角的节点，那里就是第一个被访问的节点。
怎么找下一个？从根一路向左压栈，走到最左下角。当前定位到节点 8——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 8（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 8 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？左子树已全部访问完，弹回栈顶的父节点。当前定位到节点 4——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 4（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 4 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？进入上一节点的右子树后，再一路向左到底。当前定位到节点 9——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 9（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 9 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？左子树已全部访问完，弹回栈顶的父节点。当前定位到节点 2——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 2（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 2 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9, 2]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？进入上一节点的右子树后，再一路向左到底。当前定位到节点 10——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 10（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 10 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9, 2, 10]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？左子树已全部访问完，弹回栈顶的父节点。当前定位到节点 5——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 5（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 5 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9, 2, 10, 5]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？进入上一节点的右子树后，再一路向左到底。当前定位到节点 11——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 11（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 11 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9, 2, 10, 5, 11]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？左子树已全部访问完，弹回栈顶的父节点。当前定位到节点 1——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 1（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 1 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9, 2, 10, 5, 11, 1]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？进入上一节点的右子树后，再一路向左到底。当前定位到节点 12——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 12（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 12 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9, 2, 10, 5, 11, 1, 12]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？左子树已全部访问完，弹回栈顶的父节点。当前定位到节点 6——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 6（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 6 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9, 2, 10, 5, 11, 1, 12, 6]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？进入上一节点的右子树后，再一路向左到底。当前定位到节点 13——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 13（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 13 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？左子树已全部访问完，弹回栈顶的父节点。当前定位到节点 3——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 3（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 3 访问完，加入中序结果（蓝色=已访问）。中序结果现在是 [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3]。接着去访问它的右子树（同样先访问右子树里最左的节点）。
怎么找下一个？进入上一节点的右子树后，再一路向左到底。当前定位到节点 7——它的左子树（如果有）已经全部访问完了，所以现在轮到它。
正在访问节点 7（橙色）。中序的规则是「左 → 根 → 右」：它的左子树已经处理完，现在把这个「根」输出。
节点 7 访问完，加入中序结果（蓝色=已访问）。整棵树的中序遍历完成，结果是 [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 7]。
全部 13 个节点都按「左 → 根 → 右」访问完了（绿色）。最终中序遍历结果 = [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 7]。每个节点都满足：它的整个左子树排在它前面、整个右子树排在它后面。
边界都很简单：空树返回空，单节点返回自己。
两个高频追问：递归 vs 迭代、Morris 遍历降空间。
参考代码
def inorderTraversal(root): res, stack = [], [] cur = root while stack or cur: while cur: # 一路向左压栈 stack.append(cur) cur = cur.left cur = stack.pop() # 弹出即访问（左已处理完） res.append(cur.val) # 访问根 cur = cur.right # 再转向右子树 return res复杂度
- 时间：O(n)，每个节点恰好入栈、出栈各一次
- 空间：O(H)，栈最多存一条从根到叶的路径，H 为树高（最坏 O(n)）
易错点
面试追问把动画讲成自己的话
追问递归和迭代两种写法，面试更推荐哪个？
追问有没有 O(1) 额外空间的中序遍历？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题