二叉树后序遍历的 C++ 迭代法实现与深度解析

递归的优势在于：函数调用栈会自动维护「回溯顺序」，无需手动记录节点状态 —— 访问完左子树后，自然回溯到父节点，再访问右子树，最后处理根节点。

但递归的局限性也很明显：

• 函数调用栈有深度限制（树深超过 1e4 时会栈溢出）；
• 函数调用有额外开销，在性能敏感场景下不如迭代高效；
• 进阶要求明确要求实现迭代算法，考察对遍历本质的理解。

迭代法的核心难点

迭代法需要手动用栈模拟递归的「回溯过程」，但后序遍历的「左→右→根」顺序存在一个关键矛盾：

• 访问根节点前，必须先确认左、右子树都已遍历完毕；
• 栈只能存储节点，无法直接记录「子树是否已处理」的状态；
• 若单纯按「根→左→右」顺序压栈，会导致根节点被提前访问，违背后序规则。

这也是迭代法实现的关键。如何精准判断「右子树是否已处理」，成为迭代法实现的核心。

二、常见误区：从'想当然'到'精准修正'

初始错误思路（复刻前序遍历）

由于前序遍历的迭代写法（根→左→右）非常简洁，初学者常照搬逻辑，仅调整压栈顺序：

// 错误代码：本质是「根→右→左」，反转后才是后序
vector<int> postorderTraversal(TreeNode* root) {
    vector<int> ans;
    if (!root) return ans;
    stack<TreeNode*> st;
    st.push(root);
    while (!st.empty()) {
        TreeNode* curr = st.top();
        st.pop();
        ans.push_back(curr->val); // 先访问根节点（错误核心）
        if (curr->left) st.push(curr->left); // 先压左
        if (curr->right) st.push(curr->right); // 后压右
    }
    return ans;
}

错误分析

以示例 1 的树（1→2→3）为例，错误代码的执行流程：

1. 压栈 1 → 弹 1 访问 → ans=[1] → 压左（null）、压右 2 → 栈：[2]；
2. 弹 2 访问 → ans=[1,2] → 压左 3、压右（null）→ 栈：[3]；
3. 弹 3 访问 → ans=[1,2,3]；最终结果为 [1,2,3]，与正确答案 [3,2,1] 完全相反。

核心错误：后序遍历要求「根节点最后访问」，但该写法先访问根节点，导致顺序完全颠倒 —— 本质是「根→右→左」的前序变种，而非后序。

关键认知突破：后序遍历的本质是「前序逆序」

既然错误写法得到的是「根→右→左」，而后序是「左→右→根」，两者恰好是逆序关系！这启发了第一个可行方案：

1. 按「根→右→左」顺序遍历（通过调整压栈顺序实现）；
2. 将遍历结果反转，得到「左→右→根」的后序遍历。

这个思路的优势是无需判断子树状态，完全复用前序遍历的逻辑，仅需添加反转步骤 —— 适合快速 AC，但不够贴合后序遍历的本质。

三、核心解法：从'技巧型'到'本质型'

解法一：技巧型（前序逆序法）

原理

• 前序遍历（根→左→右）→ 调整压栈顺序为「先左后右」→ 得到「根→右→左」；
• 反转「根→右→左」的结果 → 得到「左→右→根」（后序遍历）。

C++ 代码实现

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        if (root == nullptr) return ans;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            TreeNode* curr = st.top();
            st.pop();
            ans.push_back(curr->val); // 按「根→右→左」收集
            // 关键：先压左子树，再压右子树（栈后进先出，确保先访问右子树）
            if (curr->left != nullptr) {
                st.push(curr->left);
            }
            if (curr->right != nullptr) {
                st.push(curr->right);
            }
        }
        reverse(ans.begin(), ans.end()); // 反转得到后序
        return ans;
    }
};

实例演示（示例 1：root = [1,null,2,3]）

1. 压栈 1 → 弹 1 访问 → ans=[1] → 压左（null）、压右 2 → 栈：[2]；
2. 弹 2 访问 → ans=[1,2] → 压左 3、压右（null）→ 栈：[3]；
3. 弹 3 访问 → ans=[1,2,3]；
4. 反转 ans → [3,2,1]（正确结果）。

优缺点

• 优点：代码简洁，无需复杂判断，复用前序遍历逻辑，易写易记；
• 缺点：依赖反转操作（额外 O(n) 时间，虽可忽略），未体现后序遍历的本质。

解法二：本质型（prev 指针标记法）

这是最能体现后序遍历本质的解法，核心是用 prev 指针记录「上一个访问的节点」，通过判断「当前节点的右子树是否已处理」，决定是否访问当前节点。

核心原理

1. 栈的作用：存储待处理的节点，优先压入左子树节点，模拟「先左后右」的遍历顺序；
2. prev 指针的核心作用：标记「已处理完毕的节点」—— 后序遍历中，只有当右子树为空或右子树的根节点是 prev 时，说明右子树已处理，才能访问当前根节点；
3. 遍历逻辑：
   • 第一步：一路向左压栈，直到左子树为空（确保左子树优先处理）；
   • 第二步：弹出栈顶节点，判断右子树状态；
   • 第三步：若右子树未处理，重新压栈当前节点，转向右子树；若已处理，访问当前节点，更新 prev。

C++ 代码实现

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) return res;
        stack<TreeNode*> stk;
        TreeNode* prev = nullptr; // 标记上一个访问的节点（已处理完毕）
        while (root != nullptr || !stk.empty()) {
            // 第一步：一路向左深探，压入所有左子树节点（确保左优先）
            while (root != nullptr) {
                stk.emplace(root);
                root = root->left;
            }
            // 第二步：弹出栈顶节点（当前子树的根）
            root = stk.top();
            stk.pop();
            // 关键判断：右子树是否已处理（空或已访问）
            if (root->right == nullptr || root->right == prev) {
                res.emplace_back(root->val); // 访问根节点（左、右均已处理）
                prev = root; // 更新 prev 为当前节点（标记为已处理）
                root = nullptr; // 置空 root，下一轮直接从栈取节点（回溯）
            } else {
                // 右子树未处理：重新压栈当前根，转向右子树
                stk.emplace(root);
                root = root->right; // 处理右子树（右子树也会先深探左子树）
            }
        }
        return res;
    }
};

实例演示（示例 1：root = [1,null,2,3]）

目标结果：[3,2,1]

1. 初始化：res=[], stk=[], prev=null, root=1；
2. 外层循环（root=1≠null）：
   • 内层循环：root=1→压栈→root=null（左子树为空）；
   • 弹出 root=1，判断右子树（2≠prev=null）→ 重新压栈 1→stk=[1]；root=2；
3. 外层循环（root=2≠null）：
   • 内层循环：root=2→压栈→root=3→压栈→root=null（左子树为空）；
   • 弹出 root=3，判断右子树（null）→ 满足条件；res.emplace_back(3)→res=[3]；prev=3；root=null；
4. 外层循环（stk 非空：[1,2]）：
   • 弹出 root=2，判断右子树（null==prev=3？否，但右子树为空）→ 满足条件；res.emplace_back(2)→res=[3,2]；prev=2；root=null；
5. 外层循环（stk 非空：[1]）：
   • 弹出 root=1，判断右子树（2==prev=2）→ 满足条件；res.emplace_back(1)→res=[3,2,1]；prev=1；root=null；
6. 外层循环结束，返回结果。

优缺点

• 优点：无额外反转操作，完全贴合后序遍历本质，空间效率最优，面试加分；
• 缺点：需理解 prev 指针的标记逻辑，代码稍复杂，需多练习掌握。

四、多解法对比：选择适合你的方案

• 日常刷题 / 快速 AC：前序逆序法（简洁高效）；
• 面试 / 深入理解：prev 指针标记法（展示逻辑深度）；
• 递归法：适合作为基准验证结果，不推荐单独作为迭代题答案。

五、复杂度分析

时间复杂度：O(n)

• 每个节点入栈、出栈各 1-2 次（prev 指针标记法最多 2 次），但每个节点最终只访问 1 次（加入结果集 1 次）；
• 无冗余遍历操作，所有操作均为线性时间。

空间复杂度：O(h)

• h 为树的高度，栈最多存储树的一层节点（最坏情况为链状树，h=n，空间复杂度 O(n)）；
• 无额外辅助空间（prev 指针和结果数组不计入额外空间）。

六、实际应用场景

后序遍历的核心特性是「先处理子树，再处理父节点」，在工程实践中有明确应用：

1. 树形结构的资源释放：如文件系统目录删除，需先删除子目录 / 文件（左、右子树），再删除当前目录（根节点）；
2. 表达式树求值：后序遍历可按「操作数→操作数→运算符」的顺序计算，契合后缀表达式的求值逻辑；
3. 二叉树的后续处理：如统计子树节点数、计算子树高度，需先获取左、右子树的结果，再计算当前节点的结果。

七、注意事项与扩展

注意事项

1. 空树处理：所有解法均需先判断 root==nullptr，直接返回空结果，避免空指针错误；
2. 栈的操作顺序：前序逆序法中，压栈顺序为「先左后右」，确保弹出时「先右后左」；
3. prev 指针的更新：只有当节点被访问（加入结果集）后，才能更新 prev，否则会导致状态判断错误。

扩展问题（同类型遍历）

掌握后序遍历的迭代逻辑后，可快速迁移到中序遍历（左→根→右），只需调整「访问根节点」的时机：

• 中序遍历迭代法：一路向左压栈→弹出节点时直接访问（无需判断右子树）→ 转向右子树；
• 核心差异：中序遍历无需等待右子树处理，弹出栈顶节点即可访问（根在左子树之后、右子树之前）。

八、总结：解题思维的迁移

本题的核心启示在于：迭代法的本质是「手动模拟递归的回溯过程」，而难点在于「状态记录」—— 当递归的 '天然记忆' 消失时，需要用额外的指针（如 prev）或技巧（如结果反转）来弥补。

刷题的关键不是 '记住代码'，而是 '理解问题的核心矛盾'—— 后序遍历的矛盾是「根节点的访问时机」，解决了这个矛盾，迭代法自然水到渠成。如果暂时没有思路，建议先从递归写法入手，拆解其回溯过程，再尝试用栈手动模拟，逐步培养迭代思维。