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

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

1. 定义一个栈，将根节点压入栈中。
2. 定义一个变量 lastVisit 来记录上一次访问的节点。
3. 循环执行以下操作，直到栈为空：
- 将栈顶节点出栈，如果该节点的右子树为空或者已经访问过，则访问该节点，并将 lastVisit 设置为该节点。
- 否则，将该节点再次压入栈中，并将其右子树入栈。
- 如果该节点的左子树不为空且上一次访问的节点不是该节点的左子节点和右子节点，则将其左子树入栈。

下面是 C++ 实现代码：

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

该算法的时间复杂度为 O(n)，空间复杂度为 O(h)，其中 h 为树的高度。