先序遍历用栈因需模拟递归的根→左→右顺序，而栈LIFO特性要求先压右子树再压左子树，确保左子树先弹出；须判空避免nullptr解引用。

先序遍历为什么用栈且要先压右子树再压左子树

非递归先序遍历的核心是模拟递归调用栈的执行顺序：根 → 左 → 右。但栈是后进先出，所以必须把右子树先入栈、左子树后入栈，才能保证左子树先被处理。

常见错误是左右子树入栈顺序颠倒，导致输出变成“根→右→左”；另一个坑是忘记判空——nullptr不能入栈，否则解引用会崩溃。

• 初始化栈，若根不为空，将 root 入栈
• 循环直到栈空：弹出节点 node，访问它（如 cout val）
• 若 node->right 非空，入栈；若 node->left 非空，入栈

中序遍历的关键在于“一路向左到底，再回退”

中序要求左→根→右，非递归实现本质是手动维护递归中的“未访问的根节点等待区”。每次走到最左端后，才开始弹栈访问，然后转向右子树。

容易漏掉的点：进入右子树后，不能直接把它当新根处理，而要再次执行“向左探到底”的逻辑——也就是要把 node = node->right 后继续 while 循环。

立即学习“C++免费学习笔记（深入）”；

C++14

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

下载

• 从 root 开始，沿 left 指针不断入栈，直到 nullptr
• 弹栈得到 node，访问它
• 令 node = node->right，回到上一步继续向左探底

后序遍历最难——需要区分“刚入栈”和“左右子树都已处理完”

后序（左→右→根）无法像前两种那样靠简单入栈顺序解决，因为根必须最后访问。常见做法是用一个辅助标记栈，或复用原栈但加状态标识。更简洁的方案是用两个栈：第一个按“根→左→右”压入，第二个按出栈顺序接收，最终第二个栈的弹出序列就是后序。

单栈+标记法容易出错的地方是判断条件写成 !node->left && !node->right——这只能捕获叶子节点，漏掉“左右均已访问完毕的非叶节点”。正确逻辑应依赖额外状态记录。

• 双栈法：栈1压 root；每次弹栈1元素，压入栈2；再将其 left、right 依次压栈1
• 最后逐个弹栈2并访问，即得后序
• 若坚持单栈，建议为每个节点配一个 bool visited 字段，或用 std::pair<treenode bool></treenode>

统一框架：用 std::stack<:pair int>></:pair> 模拟递归状态

这个技巧能统一三种遍历逻辑：int 表示当前节点所处阶段（0=未访问子树，1=左子树已处理，2=右子树已处理）。访问顺序由状态值决定，避免重复压栈和逻辑分支混乱。

性能上多一次整数比较，但代码可读性显著提升；兼容性无问题，C++11 起完全支持。唯一要注意的是初始状态设为 0，且只有状态为 2 时才真正访问节点。

• 压入 {root, 0}
• 循环：弹出 {node, state}；若 state == 0，压入 {node, 1}，再压 {node->left, 0}
• 若 state == 1，压入 {node, 2}，再压 {node->right, 0}
• 若 state == 2，访问 node

后序的边界情况最多，比如空树、单节点、只有左或右子树——这些在统一框架里自然被覆盖，但手写双栈或单栈时极易漏判。