后序遍历非递归实现的关键是使用单栈配合last指针判断右子树是否已访问，先沿左路入栈，再根据右子树状态决定访问节点或转向右子树，最后更新last指针。
在C++中实现二叉树的后序遍历非递归方式，关键在于模拟系统栈的行为，同时确保每个节点在左右子树都访问完毕后再处理自身。与前序和中序不同，后序遍历的非递归实现稍复杂，需要额外判断是否已经访问过子树。
使用单栈实现后序遍历（推荐方法）
核心思路是利用一个栈记录待处理的节点，并用一个指针记录上一次访问的节点，以此判断当前节点的右子树是否已访问。
- 从根节点开始，将所有“左路”节点入栈（类似中序遍历）
- 取栈顶节点，但不立即弹出，检查其右子树是否为空或已被访问
- 若满足条件，则访问该节点并弹出；否则进入右子树继续处理
- 用 last 指针记录最近访问的节点，避免重复进入右子树
代码实现如下：
```cpp #includestruct TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} };
void postorderTraversal(TreeNode* root) { if (!root) return;
stack<TreeNode*> stk;
TreeNode* last = nullptr; // 记录上一个访问的节点
TreeNode* curr = root;
while (curr || !stk.empty()) {
// 一路向左入栈
while (curr) {
stk.push(curr);
curr = curr->left;
}
// 取栈顶，不弹出
curr = stk.top();
// 如果右子树为空，或右子树已访问过
if (!curr->right || curr->right == last) {
cout << curr->val << " ";
stk.pop();
last = curr; // 更新最后访问节点
curr = nullptr; // 避免重复进入左子树
} else {
curr = curr->right; // 进入右子树
}
}}
立即学习“C++免费学习笔记（深入）”；
<H3>双栈法（易于理解）</H3>
<p>另一种方法是使用两个栈：第一个栈按“根→右→左”的顺序压入节点，第二个栈用于反转输出顺序，最终得到“左→右→根”。</p>
<font color="#000000">
<ul>
<li>先将根入栈1</li>
<li>每次从栈1弹出节点，压入栈2，并依次将左、右孩子压入栈1</li>
<li>最后依次弹出栈2，即为后序结果</li>
</ul>
</font>
<p>代码示例：</p>
```cpp
void postorderTwoStacks(TreeNode* root) {
if (!root) return;
stack<TreeNode*> stk1, stk2;
stk1.push(root);
while (!stk1.empty()) {
TreeNode* node = stk1.top(); stk1.pop();
stk2.push(node);
if (node->left) stk1.push(node->left);
if (node->right) stk1.push(node->right);
}
// 输出栈2
while (!stk2.empty()) {
cout << stk2.top()->val << " ";
stk2.pop();
}
}注意事项与技巧
单栈法空间效率更高，是面试常见写法。关键点在于 last 指针的使用，它解决了“如何判断右子树已访问”的问题。双栈法逻辑清晰，适合初学者理解后序的本质——逆前序的一种变形。
测试时建议构造如下树验证：
1
/ \
2 3
/
4
正确输出应为：4 2 3 1
基本上就这些，掌握单栈法足以应对大多数场景。
