二叉树的中序遍历 图解题解
中序遍历的递归版只有三行，但不用递归时怎么办？用栈模拟。
中序遍历就像把一棵树里每个节点的「待办事项」都交给了一摞便利贴：往左走一步就贴一张「回头还要访问我」，走到头了翻出最顶上那张访问它，然后转向它的右孩子继续贴新的。这摞便利贴就是栈，它帮你记住了所有「还没轮到但迟早要回来」的节点，让你不靠系统递归也能把顺序走对。
这道题到底在问什么
- 树
- 根 4，左子树 2 挂着 (1,3)，右孩子是叶子 6
- 中序输出
- [1, 2, 3, 4, 6]
最优解：一步一步想明白
- 3递归版只有「递归左、访问根、递归右」三行。可它把真正的执行顺序都交给了系统调用栈——你看不见现在轮到谁、回头还要访问谁。面试官一句「别用递归」，很多人就卡住了。
- 4递归的本质就是：一路往左压栈，到底了弹出来访问，再转向右子树。我们自己拿一个栈来做这件事——压栈代替往左递归，弹栈访问代替轮到自己，转右代替递归右子树。栈替你记住了回头要访问谁。
- 5cur=4 → push 4 → 往左cur 从根 4 出发。规矩很简单：只要 cur 不空，就把它压栈、再往左走。把 4 压栈，cur 移到左孩子 2。
- 6cur=2 → push 2 → 往左cur=2 不空，继续压栈、往左：2 入栈，cur 移到左孩子 1。栈里现在记着「4、2 都还没轮到访问」。
- 7cur=1 → push 1 → 往左变空cur=1 还不空，再压一次：1 入栈，往左走。可 1 没有左孩子，cur 变成空——一路向左到底了。
- 8cur 空 → pop 1 → 收集 → res=[1]cur 空了，说明左边走到头：弹出栈顶 1，访问它，结果加 1。这就是中序的「根」时机——左子树走完，才轮到自己。1 没有右孩子，cur 还是空。
- 9cur 空 → pop 2 → 收集 → res=[1,2]cur 还是空，继续弹栈访问：弹出 2，结果加 2。对 2 来说左孩子 1 已访问，现在轮到根。访问完转向右孩子 3，cur=3。
- 10cur=3 → push 3 → 往左变空cur=3 不空，又回到「压栈、往左」：3 入栈往左走。3 没有左孩子，cur 马上变空——压完立刻就要弹出来访问。
- 11cur 空 → pop 3 → 收集 → res=[1,2,3]cur 空，弹出 3，结果加 3。3 也没有右孩子，cur 仍空。左子树 1、2、3 至此全部访问完，栈里只剩根 4。
- 12cur 空 → pop 4 → 收集 → res=[1,2,3,4]cur 空，弹出栈顶 4，结果加 4。4 的左子树全走完了，这才轮到根。访问完转向右孩子 6，cur=6。栈暂时空了，但 cur 不空，还没结束。
- 13cur=6 → push 6 → 往左变空cur=6 不空，照旧压栈、往左：6 入栈往左走。6 是叶子没有左孩子，cur 变空。
- 14cur 空 → pop 6 → 收集 → res=[1,2,3,4,6]cur 空，弹出 6，结果加 6。现在栈空、cur 也空，循环结束。最终结果 [1,2,3,4,6]，正好升序——这是 BST 中序遍历的招牌性质。
- 15看节点 2:① push 2 ② 左走完弹出收集 ③ 转右孩子 3把焦点放在一个节点 2 上，慢镜头重看它的一生：第一幕压栈，把自己记下、先去探左边；第二幕弹出，左边(1)全走完了才轮到它被收集；第三幕转右，cur 交给右孩子 3。每个节点都走这三幕，遍历就完成了。
- 18所有「不用递归改写遍历」的题，本质都是自己拿一个栈、模拟系统帮你做的事：下钻就压栈、该处理某节点就弹出来、处理完转向下一个方向。中序把「访问」放在弹栈之后、转右之前;换个位置就是前序或后序。
- 24把这套「压左→弹访问→转右」练到能脱稿，就去同类题迁移:前序、后序只是挪动收集时机;BST 第 k 小、验证 BST 都是在中序途中加判断。想多练，点开右侧「二叉树·遍历」专题，或问问 AI 助教帮你出几道变体。
⚠️ 容易写错的地方
✗ 错：把「访问根」写在压栈的那一刻(变成了前序)
✓ 对：必须在弹栈之后、转右之前才 ans.append(cur.val)
中序是左根右:先把左边一路压到底，弹出来时左子树已走完，这时访问才是「根」的正确时机;写在压栈时就成了根左右(前序)
✗ 错：外层循环只写 while stack
✓ 对：while cur or stack
访问完一个节点转到 cur.right 后栈可能暂时为空(如访问完根 4 那一刻)，但右子树还没走;只判 stack 会提前退出、漏掉右子树
✗ 错：压栈后忘了 cur = cur.left，或漏了转 cur = cur.right
✓ 对：内层往左、访问后往右，两个方向都不能少
不往左会死循环压同一个节点;不转右则永远走不进右子树
完整代码（Python / C++ / Java）
Python
class Solution:
def inorderTraversal(self, root):
ans = []
stack = []
cur = root
while cur or stack:
while cur: # 一路压左到底
stack.append(cur)
cur = cur.left
cur = stack.pop() # 弹出并访问
ans.append(cur.val)
cur = cur.right # 转向右子树
return ansC++
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans; stack<TreeNode*> stk;
TreeNode* cur = root;
while (cur || !stk.empty()) {
while (cur) { stk.push(cur); cur = cur->left; }
cur = stk.top(); stk.pop();
ans.push_back(cur->val);
cur = cur->right;
}
return ans;
}
};Java
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stk.isEmpty()) {
while (cur != null) { stk.push(cur); cur = cur.left; }
cur = stk.pop();
ans.add(cur.val);
cur = cur.right;
}
return ans;
}
}套路模板 · 迭代中序骨架(挖空背诵)
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(④ 转右)vector<int> res; stack<TreeNode*> stk;
TreeNode* cur = root;
while (cur || !stk.empty()) { // ①
while (cur) { // ② 一路压左
stk.push(cur);
cur = ____; // 填:cur->left
}
cur = stk.top(); stk.pop(); // ③ 弹出访问
res.push_back(____); // 填:cur->val
cur = ____; // 填:cur->right(④)
}List<Integer> res = new ArrayList<>();
Deque<TreeNode> stk = new ArrayDeque<>();
TreeNode cur = root;
while (cur != null || !stk.isEmpty()) { // ①
while (cur != null) { // ② 一路压左
stk.push(cur);
cur = ____; // 填:cur.left
}
cur = stk.pop(); // ③ 弹出访问
res.add(____); // 填:cur.val
cur = ____; // 填:cur.right(④)复杂度
时间复杂度
O(n)
每个节点恰好入栈一次、出栈一次，共 2n 次操作
空间复杂度
O(h)
栈里最多同时存一条「根到当前」的左侧路径，长度就是树高 h;链状最坏退化成 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二叉树的中序遍历 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么访问时机是「弹栈时」而不是「压栈时」？+
压栈代表「还要先处理它的左子树」;只有左子树全部压完、轮到它被弹出，才说明左边走完了，这时访问才符合左根右。写在压栈时就成了前序(根左右)。
迭代和递归版怎么选？+
递归三行更短，但栈深等于树高、不能中途暂停;迭代用显式栈，能在遍历途中停下(如求 BST 第 k 小，数到 k 个就返回)，更灵活也不怕爆栈。
还有没有 O(1) 空间的做法？+
有，Morris 中序遍历:用叶子的空右指针临时指回前驱，遍历完再拆掉，空间 O(1)。代价是会临时改动树结构、代码更绕，面试能说出名字加思路即可。
时间和空间复杂度各是多少？+
时间 O(n)，每个节点恰好进栈出栈各一次;空间 O(h)，栈里最多存一条根到最左叶的路径，最坏链状 O(n)。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。