C++实现二叉树的后序遍历(非递归) _ 双栈法逻辑详述【源码】-C++-PHP中文网

后序非递归必须用双栈，单栈无法判断左右子树是否均已访问；双栈法通过s1生成“根→右→左”序列并压入s2，再弹出s2即得左→右→根的后序序列。

c++实现二叉树的后序遍历(非递归) _ 双栈法逻辑详述【源码】

为什么后序非递归必须用双栈，单栈不行

单栈模拟后序遍历时，核心矛盾在于：你无法在弹出节点的瞬间判断「它的左右子树是否都已访问过」。中序可以靠「左链压到底再弹」来锚定访问时机，前序靠「先访根再压右左」就能保证顺序，但后序要求左→右→根，而根必须最后出现——这意味着根节点得在它两个子树全部处理完之后才输出。单栈没有额外状态记录，一旦弹出根，就丢失了“右子树还没走”的上下文。

双栈法绕开了这个状态管理难题：它不直接求后序，而是先构造一个「根→右→左」的序列（这和前序只差压栈顺序），再把整个序列倒过来——而栈天然支持倒序，所以第二栈就是个缓冲容器。

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++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

把 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 缓存友好，这点开销几乎不可测。