二叉树的中序遍历

递归版只有「递归左、访问根、递归右」三行。可它把真正的执行顺序都交给了系统调用栈——你看不见现在轮到谁、回头还要访问谁。面试官一句「别用递归」，很多人就卡住了。

递归的本质就是：一路往左压栈，到底了弹出来访问，再转向右子树。我们自己拿一个栈来做这件事——压栈代替往左递归，弹栈访问代替轮到自己，转右代替递归右子树。栈替你记住了回头要访问谁。

一路压左 · 4 入栈：cur 从根 4 出发。规矩很简单：只要 cur 不空，就把它压栈、再往左走。把 4 压栈，cur 移到左孩子 2。

一路压左 · 2 入栈：cur=2 不空，继续压栈、往左：2 入栈，cur 移到左孩子 1。栈里现在记着「4、2 都还没轮到访问」。

一路压左 · 1 入栈 · 到底：cur=1 还不空，再压一次：1 入栈，往左走。可 1 没有左孩子，cur 变成空——一路向左到底了。

到底 · 弹栈访问 1：cur 空了，说明左边走到头：弹出栈顶 1，访问它，结果加 1。这就是中序的「根」时机——左子树走完，才轮到自己。1 没有右孩子，cur 还是空。

cur 仍空 · 弹栈访问 2：cur 还是空，继续弹栈访问：弹出 2，结果加 2。对 2 来说左孩子 1 已访问，现在轮到根。访问完转向右孩子 3，cur=3。

转右 · 3 入栈 · 立刻到底：cur=3 不空，又回到「压栈、往左」：3 入栈往左走。3 没有左孩子，cur 马上变空——压完立刻就要弹出来访问。

到底 · 弹栈访问 3：cur 空，弹出 3，结果加 3。3 也没有右孩子，cur 仍空。左子树 1、2、3 至此全部访问完，栈里只剩根 4。

cur 空 · 弹栈访问根 4：cur 空，弹出栈顶 4，结果加 4。4 的左子树全走完了，这才轮到根。访问完转向右孩子 6，cur=6。栈暂时空了，但 cur 不空，还没结束。

转右 · 6 入栈：cur=6 不空，照旧压栈、往左：6 入栈往左走。6 是叶子没有左孩子，cur 变空。

完成 · 弹栈访问 6 · 升序：cur 空，弹出 6，结果加 6。现在栈空、cur 也空，循环结束。最终结果 [1,2,3,4,6]，正好升序——这是 BST 中序遍历的招牌性质。

灵魂帧慢放 · 一个节点的「压左→弹访问→转右」：把焦点放在一个节点 2 上，慢镜头重看它的一生：第一幕压栈，把自己记下、先去探左边；第二幕弹出，左边(1)全走完了才轮到它被收集；第三幕转右，cur 交给右孩子 3。每个节点都走这三幕，遍历就完成了。

所有「不用递归改写遍历」的题，本质都是自己拿一个栈、模拟系统帮你做的事：下钻就压栈、该处理某节点就弹出来、处理完转向下一个方向。中序把「访问」放在弹栈之后、转右之前;换个位置就是前序或后序。

边界三连：三个极端:空树、单节点、退化成一条链。链状是空间最坏情况，栈会同时存下整条路径。三种都能跑对，主逻辑就稳了。

面试追问：四个高频追问:访问时机、迭代对比递归、Morris 优化、复杂度。把动画里的状态和边界讲成自己的话，就答得稳。

迁移阶梯：把这套「压左→弹访问→转右」练到能脱稿，就去同类题迁移:前序、后序只是挪动收集时机;BST 第 k 小、验证 BST 都是在中序途中加判断。想多练，点开右侧「二叉树·遍历」专题，或问问 AI 助教帮你出几道变体。