Appearance
后序遍历
为什么需要后序遍历
后序遍历是二叉树三种基本深度优先遍历之一。它的访问顺序是左子树 → 右子树 → 根结点，即在访问一个结点之前，必须先处理完它的左右子树。
这种"先子后父"的特性使后序遍历在很多场景下不可替代：释放/删除整棵树时必须先删子结点再删父结点；对表达式树求值时必须先算出左右操作数才能计算当前运算符。408 考研中，后序遍历的非递归实现是三种遍历中最难的，属于高频考点。
核心思想
后序遍历的核心特点：
- 访问顺序：左子树 → 右子树 → 根结点（LRN）
- 递归定义：若树非空，先后序遍历左子树，再后序遍历右子树，最后访问根结点
- 与前序的关系：后序序列 = 前序（NRL，即"根→右→左"）序列的逆序。这一性质可用于简化非递归实现
对于下面的二叉树：
A
/ \
B C
/ \ \
D E F后序遍历结果为：D → E → B → F → C → A
交互可视化
通过下方的交互动画，你可以逐步观察后序遍历的执行过程：
操作详解
递归实现
递归实现最为直观，直接按"左→右→根"的定义编写即可。
cpp
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void PostOrder(BiTree T) {
if (T == NULL) return;
PostOrder(T->lchild); // 递归遍历左子树
PostOrder(T->rchild); // 递归遍历右子树
visit(T); // 访问根结点
}关键步骤：
- 若当前结点为空，直接返回
- 递归遍历左子树
- 递归遍历右子树
- 访问当前结点
非递归实现（双栈法）
利用后序与前序的关系：将前序遍历改为"根→右→左"，结果压入第二个栈，最后依次弹出即为后序序列。
cpp
void PostOrderDoubleStack(BiTree T) {
if (T == NULL) return;
Stack S1, S2;
InitStack(S1); InitStack(S2);
Push(S1, T);
while (!IsEmpty(S1)) {
BiTNode *p;
Pop(S1, p);
Push(S2, p); // 暂存到 S2
if (p->lchild) Push(S1, p->lchild); // 左子先入栈，后处理
if (p->rchild) Push(S1, p->rchild); // 右子后入栈，先处理
}
while (!IsEmpty(S2)) {
BiTNode *p;
Pop(S2, p);
visit(p); // 弹出顺序即为后序
}
}非递归实现（标记法）
使用一个栈和一个辅助指针 r 记录最近访问的结点，用于判断右子树是否已被访问。
cpp
void PostOrderFlag(BiTree T) {
Stack S;
InitStack(S);
BiTNode *p = T, *r = NULL; // r 指向最近访问过的结点
while (p || !IsEmpty(S)) {
if (p) { // 一路向左入栈
Push(S, p);
p = p->lchild;
} else {
GetTop(S, p); // 取栈顶（不弹出）
if (p->rchild && p->rchild != r) {
p = p->rchild; // 右子树未访问，转向右子树
} else {
Pop(S, p);
visit(p); // 左右子树均已处理，访问根
r = p; // 记录刚访问的结点
p = NULL; // 重置 p，继续弹栈
}
}
}
}关键点：当栈顶结点的右孩子为空或右孩子刚被访问过（rchild == r），说明右子树已处理完毕，此时可以访问当前结点。
两种非递归方法对比
| 方法 | 思路 | 额外空间 | 代码难度 |
|---|---|---|---|
| 双栈法 | 利用前序逆序关系 | O(n)，需两个栈 | 较简单 |
| 标记法 | 辅助指针判断右子树是否访问 | O(h)，一个栈 + 一个指针 | 较复杂 |
复杂度分析
| 实现方式 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 递归 | O(n) | O(h) | 系统栈深度为树高 h，最坏 O(n) |
| 非递归（双栈法） | O(n) | O(n) | 两个栈各最多存 n 个结点 |
| 非递归（标记法） | O(n) | O(h) | 栈深度为树高 h，最坏 O(n) |
说明：n 为结点总数，h 为树高。对于平衡二叉树 h = O(log n)，对于退化为链的单支树 h = O(n)。
考研高频考点
- ⭐ 非递归后序遍历的实现（算法设计题高频，标记法为主要考法）
- ⭐ 根据前序 + 中序 / 后序 + 中序序列还原二叉树（选择题/大题必考）
- ⭐ 后序遍历的应用：表达式树求值、计算树高、释放二叉树（概念题）
- ⭐ 后序序列与前序序列的逆序关系（选择题常考陷阱）
- 后序遍历栈中保存的结点恰好是当前结点到根的路径（可用于求最近公共祖先）
- 三种遍历序列的组合判断树的唯一性（前序+后序不能唯一确定二叉树）