二叉树后序遍历的非递归算法

二叉树的后序遍历顺序是左子树 -> 右子树 -> 根节点。下面是非递归实现二叉树后序遍历的算法：

1. 创建一个栈，将二叉树的根节点压入栈中。

2. 创建一个变量last_visited，用于记录上一个访问过的节点。

3. 当栈不为空时，执行以下操作：

a. 取出栈顶元素，将其左右子节点依次压入栈中。

b. 如果栈顶元素的左右子节点都为NULL，或者其左右子节点都已经被访问过了，则将栈顶元素弹出并输出。

c. 如果栈顶元素的左右子节点中有一个还未被访问，则将该子节点压入栈中。

4. 重复步骤3直到栈为空。

以下是C++的代码实现：

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