6、二叉树遍历的非递归实现

递归遍历二叉树，代码确实简洁优雅。但我在实际项目中遇到过一个问题——当树深度达到几千层时，递归调用栈直接爆了。嗯，那次排查花了我不少时间。

所以，非递归遍历不是炫技，是刚需。今天我们就来聊聊三种遍历的非递归写法：前序、中序、后序。核心思想都一样——用栈模拟系统调用栈。

为什么需要非递归？

递归的本质是函数调用，每次调用都会压栈。系统栈的大小是有限的，一般几MB。二叉树深度一大，递归就崩了。

非递归遍历，说白了就是自己管理一个栈。你控制入栈出栈，想怎么遍历都行。而且，非递归的效率通常更高——少了函数调用的开销。

前序遍历非递归（栈实现）

前序遍历的顺序是：根 → 左 → 右。用栈实现时，我习惯先压右孩子，再压左孩子。为什么？因为栈是后进先出，先压右，左孩子才能先出栈。

看代码：

void preorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    
    stack<TreeNode*> stk;
    stk.push(root);
    
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        
        printf("%d ", node->val);  // 访问根
        
        // 先压右，再压左
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
}

逻辑很简单：每次弹出一个节点，访问它，然后把它的右孩子和左孩子依次入栈。这样左孩子就会在下一轮先被弹出。

中序遍历非递归（栈实现）

中序遍历的顺序是：左 → 根 → 右。这个稍微绕一点。你不能直接访问根，得先把左子树处理完。

核心思路：一直往左走，把沿途节点全部入栈。走到空时，弹出栈顶访问，然后转向右子树。

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* cur = root;
    
    while (cur != NULL || !stk.empty()) {
        // 一直往左走，入栈
        while (cur != NULL) {
            stk.push(cur);
            cur = cur->left;
        }
        
        // 弹出栈顶，访问
        cur = stk.top();
        stk.pop();
        printf("%d ", cur->val);
        
        // 转向右子树
        cur = cur->right;
    }
}

你想想看，这个while循环是不是很巧妙？外层循环控制整体流程，内层循环负责「一路向左」。我刚开始学的时候，总觉得这个写法很别扭，后来写多了才发现——这才是中序遍历的本质。

后序遍历非递归（双栈法）

后序遍历的顺序是：左 → 右 → 根。这是最麻烦的一个。因为你要等左右子树都访问完，才能访问根。

双栈法是我个人最喜欢的方式。思路很简单：

• 第一个栈用来遍历，顺序是「根 → 右 → 左」
• 第二个栈用来反转，得到「左 → 右 → 根」

说白了，就是先搞一个「根右左」的遍历，然后反转一下。

void postorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    
    stack<TreeNode*> stk1, stk2;
    stk1.push(root);
    
    while (!stk1.empty()) {
        TreeNode* node = stk1.top();
        stk1.pop();
        stk2.push(node);  // 先入栈2
        
        // 先压左，再压右（和前序相反）
        if (node->left) stk1.push(node->left);
        if (node->right) stk1.push(node->right);
    }
    
    // 输出栈2的内容
    while (!stk2.empty()) {
        printf("%d ", stk2.top()->val);
        stk2.pop();
    }
}

为什么这样能行？因为stk1的遍历顺序是「根右左」，入栈2的顺序也是「根右左」。但栈2是后进先出，所以出栈顺序就变成了「左右根」——正好是后序遍历。

后序遍历非递归（标记法）

双栈法虽然好理解，但用了两个栈，空间开销大。标记法只需要一个栈，但需要给每个节点加一个「是否已访问过」的标记。

void postorderTraversalWithFlag(TreeNode* root) {
    stack<pair<TreeNode*, int>> stk;
    TreeNode* cur = root;
    
    while (cur != NULL || !stk.empty()) {
        while (cur != NULL) {
            stk.push({cur, 0});  // 0表示左子树未处理完
            cur = cur->left;
        }
        
        auto& top = stk.top();
        cur = top.first;
        int flag = top.second;
        stk.pop();
        
        if (flag == 0) {
            // 左子树处理完了，但右子树还没处理
            stk.push({cur, 1});  // 标记为1，表示右子树已处理
            cur = cur->right;
        } else {
            // 左右子树都处理完了，访问根
            printf("%d ", cur->val);
            cur = NULL;  // 重要：置空，让外层循环继续弹栈
        }
    }
}

标记法的核心就是：每个节点入栈两次。第一次入栈时标记为0，表示「左子树还没处理完」。第二次入栈时标记为1，表示「右子树也处理完了，可以访问了」。

知识体系总览

下面这张图，把三种非递归遍历的核心逻辑串起来了。我建议你多看几遍，理解每个箭头代表的含义。

总结

非递归遍历，说白了就是「手动管理栈」。前序最简单，中序最经典，后序最绕。我个人建议：

• 前序：记住「右先入，左先出」
• 中序：记住「一路向左，出栈转右」
• 后序：面试用双栈法，生产环境用标记法

我曾经在面试中被问到后序遍历的非递归实现，当时脑子一热写了双栈法，面试官点了点头。后来在实际项目中，我改用标记法——省一个栈的空间，代码也不复杂。

嗯，今天就聊到这里。代码多写几遍，自然就熟了。

---

公众号:蓝海资料掘金营，微信deep3321