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

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

1. 定义一个栈和一个指针p，初始时p指向根节点。

2. 将p节点入栈，然后将p指向其左子节点，重复此过程直到p为空。

3. 如果栈不为空，则取出栈顶节点，判断其是否存在右子节点或者是否已经被访问过。

4. 如果不存在右子节点或者右子节点已经被访问过，则访问该节点，并将其从栈中弹出。

5. 如果存在右子节点且未被访问过，则将该节点入栈，然后将p指向其右子节点。

6. 重复步骤3-5，直到栈为空。

下面是二叉树后序遍历的非递归算法实现：

void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    stack<TreeNode*> s;
    TreeNode* p = root;
    TreeNode* lastVisited = NULL;
    while (p != NULL || !s.empty()) {
        while (p != NULL) {
            s.push(p);
            p = p->left;
        }
        TreeNode* topNode = s.top();
        if (topNode->right == NULL || topNode->right == lastVisited) {
            // 右子树为空或已被访问
            cout << topNode->val << " ";
            s.pop();
            lastVisited = topNode;
        } else {
            // 右子树存在且未被访问
            p = topNode->right;
        }
    }
}

该算法的时间复杂度为O(n)，空间复杂度为O(n)，其中n为二叉树的节点数。