后序非递归必须用双栈，单栈无法判断左右子树是否均已访问；双栈法通过s1生成“根→右→左”序列并压入s2，再弹出s2即得左→右→根的后序序列。
为什么后序非递归必须用双栈，单栈不行
单栈模拟后序遍历时，核心矛盾在于：你无法在弹出节点的瞬间判断「它的左右子树是否都已访问过」。中序可以靠「左链压到底再弹」来锚定访问时机，前序靠「先访根再压右左」就能保证顺序，但后序要求左→右→根，而根必须最后出现——这意味着根节点得在它两个子树全部处理完之后才输出。单栈没有额外状态记录，一旦弹出根，就丢失了“右子树还没走”的上下文。
双栈法绕开了这个状态管理难题：它不直接求后序，而是先构造一个「根→右→左」的序列（这和前序只差压栈顺序），再把整个序列倒过来——而栈天然支持倒序，所以第二栈就是个缓冲容器。
-
s1扮演变形前序栈：每次pop一个节点，立刻push到s2；然后按「先左后右」压回s1（注意：不是先右后左） - 压栈顺序反直觉：为让
s1弹出顺序是「根→右→左」，你得先压左、再压右——因为栈 FILO，后压的右会先弹出 -
s2最终内容就是后序逆序，pop出来自然就是左→右→根
双栈法 C++ 实现要点与易错点
关键不在写对，而在写稳。下面这段代码经多个边界测试验证（空树、单节点、左偏树、右偏树）：
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
if (!root) return res;
<pre class='brush:php;toolbar:false;'>stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* node = s1.top(); s1.pop();
s2.push(node);
// 注意：这里先 push left，再 push right
if (node->left) s1.push(node->left);
if (node->right) s1.push(node->right);
}
while (!s2.empty()) {
res.push_back(s2.top()->val);
s2.pop();
}
return res;}
立即学习“C++免费学习笔记（深入）”；
常见翻车点：
- 把
s1的压栈顺序写成「先右后左」——那样s2得到的是「根→左→右」，倒过来是「右→左→根」，错 - 漏判
root == nullptr，导致s1.push(nullptr)后崩溃 - 误在
s2循环里用top()但没pop()，死循环 - 用
vector模拟栈（比如push_back/pop_back）代替stack，语义不清且易索引越界
双栈法 vs 单栈+标记法：选哪个更实际
单栈+bool标记（如 pair<treenode bool></treenode>）也能实现后序，逻辑上更贴近「我刚从哪来」的回溯感，但实际编码负担更大：每轮要拆包、判标记、决定是继续下探还是输出。双栈法虽然多用一倍内存，但逻辑线性、分支少、无状态切换，更适合面试手写或嵌入式等强调可读性与稳定性的场景。
性能上，双栈法时间复杂度仍是 O(n)，空间是 O(h)（h 为树高），和单栈法一致；但常数项略高——两套栈操作、两次遍历。不过现代 CPU 缓存友好，这点开销几乎不可测。
- 如果你在调试期，优先用双栈：错一次就能看到
s2里塞了什么，方便断点观察 - 如果树极深（>10⁵ 层）且内存敏感，考虑改用 Morris 后序（但实现复杂度陡增）
- 永远别为了“节省一个栈”去硬啃单栈 while 套 while + 标记位的写法，除非你在写底层库
层序遍历为什么不用栈而用队列
这是个容易被连带混淆的点：后序非递归用双栈，是因为它本质在做「逆序控制」；而层序遍历目标是「同层节点一起出来」，天然需要 FIFO 行为——先进来的节点，它的子节点也该排在后面节点的子节点之前被处理。队列的 push/pop 顺序正好匹配这一需求。
拿双栈去套层序只会让逻辑扭曲：你得不断在两个栈之间倒腾，还要记录层级边界，远不如一个 queue + for (int i = q.size(); i > 0; --i) 清晰。
真正容易被忽略的是：所有非递归遍历中，只有后序的双栈法存在「结果需二次反转」这个隐含步骤。其他遍历（前序、中序、层序）的结果都是边处理边收集，而双栈后序必须等 s1 空了，才能开始从 s2 取最终答案——这个延迟交付，是它区别于其他迭代法最本质的特征。
