双栈法核心逻辑是用stack1按“根右左”入栈模拟递归调用，stack2存已确定左右子树处理完毕、可输出的节点；最终从stack2弹出即得后序序列。
后序遍历双栈法的核心逻辑是什么
双栈法本质是用两个栈模拟递归调用栈 + 访问标记栈：第一个栈（stack1）存待处理节点，第二个栈（stack2）存「已确定要输出」的节点。关键在于——后序是“左右根”，但栈是后进先出，所以入栈顺序必须是“根右左”，这样从 stack2 弹出时才是“左右根”。
为什么不能直接用一个栈加 bool 标记
单栈+标记法（如 pair<treenode bool></treenode>）虽可行，但双栈法更清晰规避了重复压栈和状态管理错误。常见坑是把 stack2 当成辅助缓存乱 push，结果顺序错乱；或者误将 stack1 的 pop 节点直接加入结果，跳过了“先确保左右子树都处理完”的约束。
-
stack1只负责按“根→右→左”顺序推进，不输出 -
stack2每次 push 都代表该节点的左右子树已全部处理完毕 - 最终结果必须全部从
stack2弹出，不能边 push 边输出
C++ 实现要点与易错代码片段
注意指针判空、栈类型声明、以及循环退出条件。下面是最简可靠写法：
vector<int> postorderTraversal(TreeNode* root) {
if (!root) return {};
stack<TreeNode*> s1, s2;
s1.push(root);
while (!s1.empty()) {
TreeNode* node = s1.top(); s1.pop();
s2.push(node); // 确认该节点可输出（等会儿弹出）
if (node->left) s1.push(node->left);
if (node->right) s1.push(node->right);
}
vector<int> res;
while (!s2.empty()) {
res.push_back(s2.top()->val);
s2.pop();
}
return res;
}⚠️ 易错点：s1.push(node->left) 和 s1.push(node->right) 顺序不能反，否则变成“根左右”→前序；若用 queue 替代 s1，就退化成层序变种，完全失效。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
立即学习“C++免费学习笔记（深入）”；
和递归/单栈迭代法的性能与可读性对比
双栈法时间 O(n)，空间 O(h)（h 是树高），但实际常驻两个栈，内存开销略高于单栈标记法。可读性上，它把“访问顺序”和“输出时机”物理隔离，调试时容易跟踪 stack2 是否按预期累积。不过如果面试官明确要求“只用一个栈”，就得切回标记法或改用 Morris（但后者破坏树结构）。
真正容易被忽略的是：双栈法在空子树较多时，s2 会提前积压大量节点，而递归的栈帧天然按需分配——这点在内存受限嵌入式场景里得掂量。
