07、后序遍历迭代

注：阅读该文章前，建议各位先阅读之前的三篇文章，对该文章的理解有很大帮助。

后序遍历的相比前两种方法，难理解了一些，所以这里我们需要认真思考一下，每一行的代码的作用。

我们先来复习一下，二叉树的后序遍历

我们知道后序遍历的顺序是, 对于树中的某节点, 先遍历该节点的左子树, 再遍历其右子树, 最后遍历该节点。

那么我们如何利用栈来解决呢？

动画模拟

我们直接来看动画，看动画之前，但是我们需要带着问题看动画，问题搞懂之后也就搞定了后序遍历。

1.动画中的橙色指针发挥了什么作用

2.为什么动画中的某节点，为什么出栈后又入栈呢?

好啦，下面我们看动画吧！

后序遍历迭代

相信大家看完动画之后，也能够发现其中规律。

我们来对其中之前提出的问题进行解答

1.动画中的橙色箭头的作用？

用来定位住上一个访问节点，这样我们就知道 cur 节点的 right 节点是否被访问，如果被访问，我们则需要遍历 cur 节点。

2.为什么有的节点出栈后又入栈了呢？

出栈又入栈的原因是，我们发现 cur 节点的 right 不为 null ，并且 cur.right 也没有被访问过。因为 cur.right != preNode ，所以当前我们还不能够遍历该节点，应该先遍历其右子树中的节点。

所以我们将其入栈后，然后cur = cur.right

代码

#include <vector>
#include <stack>

// 二叉树节点定义
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:
    std::vector<int> postorderTraversal(TreeNode* root) {
        std::stack<TreeNode*> stk;  // 辅助栈
        std::vector<int> result;    // 存储遍历结果
        TreeNode* cur = root;       // 当前遍历节点指针
        TreeNode* preNode = nullptr; // 记录上一个访问的节点（用于判断右子树是否已遍历）
        
        // 循环条件：当前节点不为空 或 栈不为空
        while (cur != nullptr || !stk.empty()) {
            // 1. 遍历左子树：将所有左节点入栈，直到无左子节点
            while (cur != nullptr) {
                stk.push(cur);
                cur = cur->left;
            }
            
            // 取出栈顶节点（当前子树的根节点）
            cur = stk.top();
            stk.pop();
            
            // 判断是否可以访问当前节点：
            //    - 右子树为空（无需处理右子树）
            //    - 右子树已访问过（preNode指向右子节点）
            if (cur->right == nullptr || cur->right == preNode) {
                result.push_back(cur->val);  // 访问当前节点（后序：左→右→根）
                preNode = cur;               // 更新前驱节点为当前节点
                cur = nullptr;               // 重置当前节点，避免重复入栈左子树
            } else {
                // 右子树未访问：将当前节点重新入栈，转向右子树处理
                stk.push(cur);
                cur = cur->right;
            }
        }
        
        return result;
    }
};

时间复杂度 O（n）, 空间复杂度 O（n）

这里二叉树的三种迭代方式到这里就结束啦，大家可以进行归纳总结，三种遍历方式大同小异，建议各位，掌握之后，自己手撕一下，从搭建二叉树开始。