基于单栈的二叉树后序遍历：寻求更直观的理解方式

嘿，我完全懂这种感觉！前序迭代确实因为和递归逻辑几乎一一对应，所以上手特别顺，但后序总让人觉得绕来绕去摸不着头脑。我给你分享两个超直观的思路，帮你把它彻底搞明白～

先回顾下你熟悉的前序遍历逻辑 #

你给出的前序迭代代码逻辑很清晰：

void iterativePreorder(node *root) {
    // Base Case
    if (root == NULL) return;
    // Create an empty stack and push root to it
    stack<node *> nodeStack;
    nodeStack.push(root);
    /* Pop all items one by one. Do following for every popped item
       a) print it
       b) push its right child
       c) push its left child
       Note that right child is pushed first so that left is processed first */
    while (nodeStack.empty() == false) {
        // Pop the top item from stack and print it
        struct node *node = nodeStack.top();
        printf ("%d ", node->data);
        nodeStack.pop();
        // Push right and left children of the popped node to stack
        if (node->right)
            nodeStack.push(node->right);
        if (node->left)
            nodeStack.push(node->left);
    }
}

核心就是根→左→右的顺序，利用栈“后进先出”的特性，先压右孩子再压左孩子，保证弹出时左孩子先被处理。

思路一：反转「根→右→左」的遍历结果 #

后序遍历的顺序是左→右→根，你会发现它刚好是「根→右→左」顺序的反转。那我们可以基于前序的逻辑改一改：

1. 把前序里“先压右孩子再压左孩子”改成先压左孩子再压右孩子，这样遍历顺序就变成了「根→右→左」
2. 不要直接打印节点，而是把节点值存到一个列表里
3. 遍历结束后，把列表反转，就得到了后序遍历的结果

对应的代码示例（和你的前序代码风格保持一致）：

void iterativePostorderReverse(node *root) {
    if (root == NULL) return;
    stack<node *> nodeStack;
    vector<int> result;
    nodeStack.push(root);
    
    while (!nodeStack.empty()) {
        struct node *node = nodeStack.top();
        result.push_back(node->data); // 先存起来，不打印
        nodeStack.pop();
        
        // 先压左孩子，再压右孩子，保证弹出时右孩子先处理
        if (node->left)
            nodeStack.push(node->left);
        if (node->right)
            nodeStack.push(node->right);
    }
    
    // 反转结果，得到左→右→根
    reverse(result.begin(), result.end());
    for (int val : result) {
        printf("%d ", val);
    }
}

这个方法完全基于你已经掌握的前序逻辑，几乎不需要额外理解新东西，特别适合入门。

思路二：用栈记录节点的访问状态 #

另一种更“正统”的思路是给每个节点加一个「是否已访问」的标记，解决后序中“需要先处理子树再访问自己”的问题：

• 栈里存储的不是单纯的节点，而是「节点指针 + 布尔值」的组合（布尔值表示该节点是否已经被处理过）
• 初始时把根节点压入栈，标记为未访问
• 循环弹出栈顶元素：
  • 如果是未访问：说明我们第一次遇到这个节点，需要先处理它的左右子树。所以把它重新压入栈，标记为已访问，然后依次压入右孩子、左孩子（都标记为未访问）—— 这样保证左孩子先被处理
  • 如果是已访问：说明它的左右子树都已经处理完了，直接打印这个节点的值就行

对应的代码示例：

#include <stack>
#include <utility> // 用于pair

void iterativePostorderState(node *root) {
    if (root == NULL) return;
    // 栈存储pair：<节点指针，是否已访问>
    stack<pair<node*, bool>> nodeStack;
    nodeStack.push({root, false});
    
    while (!nodeStack.empty()) {
        auto [currNode, isVisited] = nodeStack.top();
        nodeStack.pop();
        
        if (isVisited) {
            // 已访问，直接打印
            printf("%d ", currNode->data);
        } else {
            // 未访问，先压回自己（标记已访问），再压右、左孩子
            nodeStack.push({currNode, true});
            if (currNode->right)
                nodeStack.push({currNode->right, false});
            if (currNode->left)
                nodeStack.push({currNode->left, false});
        }
    }
}

这个思路更贴近递归的本质（递归里每个节点会被访问两次：第一次是进入节点，第二次是处理完子树返回），理解后能更清楚迭代和递归的对应关系。

这两种方法都比那种用一个栈加前驱节点的方法直观得多，你可以先从第一种反转法入手，完全基于前序的知识过渡，再慢慢理解第二种状态标记法～

内容的提问来源于stack exchange，提问作者Vedant Dixit