中序遍历的非递归写法：用栈模拟递归

本文属于「408 算法拓展训练」——考纲内、真题代码题尚未考过的经典题。这道题和普通的「写一个遍历」不一样：递归版中序遍历人人会写，但不许用递归，只能用循环加显式栈重现同样的访问顺序——这考的是能不能看穿递归调用栈背后到底在做什么。它是经典训练题，不是真题，也不押题。

题目

给定一棵二叉树，要求写出它的中序遍历（左子树 → 根 → 右子树），但不能使用递归，必须用循环加栈的方式实现。设计算法输出中序遍历序列。

关键设计洞察：递归的「隐式栈」要显式地搬出来

递归版中序遍历只有三行：

void inorderRecursive(TreeNode *root) {
    if (root == NULL) return;
    inorderRecursive(root->left);
    printf("%d ", root->data);
    inorderRecursive(root->right);
}

它之所以能"记住"该往哪里走、走完了该回到哪里，全靠函数调用自带的调用栈：每次递归调用 inorderRecursive(root->left)，系统会把"当前这个结点还没处理完，处理完左子树要回来打印它、再处理右子树"这件事压进调用栈。写非递归版本，本质就是把这个隐式的调用栈变成一个自己管理的显式栈，手动完成"往左走到底 → 回退一层访问 → 转向右子树"这一套系统本来替你做的事。

这道题没有暴力和最优之分，是一道设计题：能不能看清递归背后的机制，决定了这段代码写不写得出来。

做法与关键细节

中序遍历"左子树 → 根 → 右子树"的顺序，翻译成显式栈的操作是一个三步循环：

1. 一路把左孩子压栈，压到底为止——这一步对应递归里"不断往下调用 inorderRecursive(root->left)，还没轮到打印"的过程；
2. 栈顶就是当前应该访问的结点，弹出并访问它——这一步对应递归里"左子树处理完了，轮到打印当前结点"；
3. 转向该结点的右孩子，重复整个过程——这一步对应递归里"打印完当前结点，接着调用 inorderRecursive(root->right)"。

#include <stdio.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

void inorderIterative(TreeNode *root) {
    TreeNode *stack[1000];
    int top = -1;
    TreeNode *cur = root;

    while (cur != NULL || top != -1) {
        while (cur != NULL) {          // 一路压左孩子到底
            stack[++top] = cur;
            cur = cur->left;
        }
        cur = stack[top--];            // 弹栈访问栈顶(左子树已处理完)
        printf("%d ", cur->data);
        cur = cur->right;              // 转向右孩子,重复整个过程
    }
}

几个决定这段代码对不对的关键细节：

• 循环条件是 cur != NULL || top != -1，不是只看栈空。cur 指针本身也承载着"还有没有子树没处理"的信息——如果只用 top != -1 判断，会在 cur 还没走到底、栈却暂时为空的中间状态提前退出循环。
• 内层 while 是"压栈+左移"，外层循环体是"弹栈+访问+右移"，两层职责不能混。内层只管往左走到底，不访问任何结点；只有弹栈的那一刻才是真正的"访问"时机。把访问逻辑写进内层循环，会让根和右子树的访问顺序整个错乱。
• 弹栈之后一定要转向右孩子，哪怕右孩子是空。cur = cur->right 这一步不能省——它让下一轮外层循环的内层 while 能够正确判断"要不要继续往左压栈"（如果右孩子非空，会开始压右子树的左链；如果右孩子是空，cur 变成 NULL，内层 while 直接跳过，外层循环转去弹栈里的下一个结点）。
• cur 指针和栈是配合工作的，不是互相替代。cur 负责"往下探路"，栈负责"记住回退路径"——这正是递归调用栈在系统层面做的两件事，被拆成了一个指针加一个显式栈。

复杂度：每个结点入栈、出栈各恰好一次，时间 $O(n)$；栈里最多同时存在一条从根到某叶子的路径上的结点，空间 $O(h)$——和递归版本的调用栈深度完全一致，只是从系统隐式管理换成了自己显式管理。

显式栈模拟递归，看一遍

用一棵七结点的二叉搜索树（根 4，左子树 2(1,3)，右子树 6(5,7)）演示非递归中序遍历——留意栈如何先把左链 4→2→1 压到底，弹出 1 访问后转向它的（空）右孩子，退回去弹出 2，再压入 3 这条新的左链：

加载可视化中...

演示为 JavaScript 版本，逻辑与上文 C 代码一一对应。输出序列 1,2,3,4,5,6,7 和递归版中序遍历的结果完全一致——非递归只是换了一种实现方式，访问顺序不变。

常见错点清单

• 忘了内层 while 的作用，把访问逻辑写进了压栈阶段：压栈阶段只管往左走，不打印、不处理右子树，这一点和递归里"还没到打印那一行"是同一个道理。
• 弹栈之后忘记 cur = cur->right：会导致栈一旦弹空、cur 还停在刚访问过的结点上，下一轮内层 while 误以为还要继续往左压栈，把同一批结点重复处理。
• 循环条件漏写 cur != NULL 这一半：只用栈是否为空判断循环结束，会在 cur 还没走到最左端、栈恰好暂时空着的中间状态提前退出，丢掉右子树的一部分结点。
• 栈数组开小了：栈的最大深度等于树高 $h$，最坏情况下（树退化成一条链）$h$ 可以等于 $n$，数组容量按结点数上限开，不能想当然按平衡树的 $\log n$ 估。
• 把中序模板套用到先序/后序上却不改变换位置：中序是"压栈时不访问，弹栈时才访问"；先序应该是"压栈前就访问"；后序需要额外记录"右子树是否已经访问过"。三种非递归写法结构相似但访问时机不同，生搬硬套会把顺序搞错。

下一步

• 看中序遍历的交互演示：中序遍历可视化
• 回到方法论源头：「暴力解到最优解」真题专题总纲