怎样实现二叉树后序遍历的非递归算法

非递归算法可以使用栈来实现二叉树的后序遍历。具体步骤如下：

1. 创建一个空栈S和一个指针p指向根节点。
2. 将p节点入栈，同时将p指向它的左子节点，直到p为空。
3. 当p为空时，从栈顶取出一个节点t，如果t的右子节点为空或者已经访问过，则访问t节点并将其标记为已访问，否则将t节点重新入栈，p指向t的右子节点。
4. 重复步骤3直到栈为空。

以下是C++代码实现：

void postorderTraversal(TreeNode* root) {
    if (!root) return;
    stack<TreeNode*> s;
    TreeNode* p = root;
    TreeNode* lastVisited = nullptr;
    while (p || !s.empty()) {
        while (p) {
            s.push(p);
            p = p->left;
        }
        TreeNode* t = s.top();
        if (!t->right || t->right == lastVisited) {
            s.pop();
            lastVisited = t;
            cout << t->val << " ";
        } else {
            p = t->right;
        }
    }
}

在算法中，lastVisited是一个指针，用于标记上次访问过的节点，以便判断t节点的右子节点是否已经访问过。