后序遍历非递归更难因需满足“左右根”顺序而栈为lifo，根节点不能在访问左子树后立即弹出，必须等待右子树处理完毕；需用标记位或双栈模拟递归的未完成状态，且bst特性对此无简化作用。
为什么后序遍历的非递归实现比前序/中序更难
因为后序遍历要求“左右根”，而栈是后进先出，访问完左子树后不能立刻弹出根——它还得等右子树也处理完。递归天然靠函数调用栈保存“我还没处理完”的状态，非递归得自己模拟这个状态。常见错误是 root 被过早弹出，导致右子树没访问就丢了根节点。
用一个栈 + 辅助标记判断是否该访问根节点
核心思路：入栈时记录“这个节点是否已访问过右子树”。可以用 pair<treenode bool></treenode>，bool 表示右子树是否已处理；也可以用额外栈存上次访问节点（更省内存但逻辑稍绕）。推荐前者，清晰不易错：
stack<pair bool>> st;
if (root) st.push({root, false});
while (!st.empty()) {
auto [node, visited] = st.top(); st.pop();
if (visited) {
result.push_back(node->val); // 真正访问
} else {
st.push({node, true}); // 标记为“右子树已处理”
if (node->right) st.push({node->right, false});
if (node->left) st.push({node->left, false});
}
}
</pair>
注意顺序：先压右、再压左，这样左子树先出栈，符合左→右→根。
用两个栈模拟系统调用栈行为
这是另一种经典解法，不依赖标记位，但空间开销略大。第一个栈做“遍历驱动”，第二个栈存最终访问顺序：
- 把
root压入栈1 - 每次从栈1弹出节点，压入栈2；然后按“左→右”顺序把子节点压入栈1（注意不是右→左）
- 最后倒序输出栈2（即用
vector逆序或直接从栈顶弹出）
关键点：stack2 中的元素顺序就是后序序列的逆序，所以最后要反转。容易漏掉这步，导致结果是“根→右→左”而非“左→右→根”。
BST特性对非递归后序遍历没有简化作用
二叉搜索树只是保证了中序遍历有序，但后序遍历本身不依赖值大小关系。无论是不是BST，非递归后序的控制逻辑完全一样。别试图用 val 比较来跳过某些分支——这会破坏遍历结构，导致漏节点或重复访问。
真正要注意的是指针安全：空节点必须跳过，nullptr 不能入栈；所有 node->left 和 node->right 访问前必须判空。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
