后序遍历非递归实现更难，因其需“左右根”顺序而栈天然支持“根左右”或“左根右”；关键难点是节点出栈时机判断——须等左右子树均访问完毕，但栈中无状态记录，故需标记法或last_visited辅助判断。
为什么后序遍历的非递归实现比前序/中序难？
因为后序遍历要“左右根”，而栈天然适合“根左右”（前序）或“左根右”（中序）。后序的关键难点在于：节点出栈时机不好判断——它必须等左右子树都访问完才能输出，但栈里只存节点指针，不记录“是否已处理过右子树”。常见错误是直接套用中序模板，结果变成“根右左”或漏掉某些节点。
用栈+标记法实现最直观的非递归后序遍历
核心思路是给每个节点配一个状态标记，表示“是否已访问过它的左右子树”。用 std::stack 存储 std::pair<treenode bool></treenode>，bool 为 true 表示左右子树已处理完毕，可输出该节点。
操作步骤：
- 初始将根节点入栈，状态为
false - 循环直到栈空：
- 取栈顶元素
node, visited - 如果
visited == true，直接输出node->val并出栈 - 否则，标记为已访问（即压入
{node, true}），再按“右、左”顺序压入子节点（注意顺序：右先于左，保证左先被处理）
- 取栈顶元素
示例片段（省略 TreeNode 定义）：
std::stack<:pair bool>> stk;
if (root) stk.push({root, false});
while (!stk.empty()) {
auto [node, visited] = stk.top(); stk.pop();
if (visited) {
result.push_back(node->val);
} else {
stk.push({node, true});
if (node->right) stk.push({node->right, false});
if (node->left) stk.push({node->left, false});
}
}</:pair>
只用一个栈 + 辅助变量的优化写法（避免 pair 开销）
用一个普通栈存节点，另设 TreeNode* last_visited 记录上一次真正输出的节点。关键判断逻辑是：node->right == last_visited 或 node->right == nullptr 且 node->left == last_visited 或 node->left == nullptr —— 这说明左右子树都已处理完。
更实用的简化判断方式：
- 若栈顶节点无左右孩子，或其右孩子就是
last_visited，或其左孩子是last_visited且右孩子为空，则可输出该节点 - 否则，先压右再压左（同上）
- 每次真正输出节点时更新
last_visited = node
这个版本节省内存，但条件判断稍易出错；调试时建议先用标记法验证逻辑，再切换到单栈版。
容易踩的坑：空节点处理与循环退出条件
常见错误包括：
- 忘记判空：对
nullptr节点调用->left或->right，直接崩溃 - 压栈顺序反了：误把“左、右”顺序压入，导致遍历顺序错乱（应右在前、左在后）
- 未更新
last_visited：在单栈版本中漏掉这步，后续判断永远不成立 - 栈空时仍尝试
top()：务必在while (!stk.empty())内部做top()和pop()
真实项目中，如果只是临时调试，建议优先用标记法；追求极致性能且确定树深度可控时，再考虑单栈+last_visited 方案。两种方法时间复杂度都是 O(n)，空间复杂度最坏 O(h)（h 为树高），但标记法常数因子略大。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
