Appearance
后序遍历
后序遍历的特点
后序遍历按"左->右->根"的顺序，最后才访问根结点，适合"先处理子问题再汇总"的场景——比如计算目录大小（先算子目录）、释放树的内存（先释放子树）。
408 考研中，后序遍历的非递归实现是三种遍历中最难的，属于高频考点。此外，后序遍历栈中保存的结点恰好构成从当前结点到根的路径，可用于求最近公共祖先。
核心思想
后序遍历的核心特点：
- 访问顺序：左子树 → 右子树 → 根结点（LRN）
- 递归定义：若树非空，先后序遍历左子树，再后序遍历右子树，最后访问根结点
- 与前序的关系：后序序列 = 前序（NRL，即"根→右→左"）序列的逆序。这一性质可用于简化非递归实现
对于下面的二叉树：
A
/ \
B C
/ \ \
D E F后序遍历结果为：D → E → B → F → C → A
交互可视化
通过下方的交互动画，你可以逐步观察后序遍历的执行过程：
操作详解
递归实现
递归实现最为直观，直接按"左→右→根"的定义编写即可。
c
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); // 访问根结点
}关键步骤：
- 若当前结点为空，直接返回
- 递归遍历左子树
- 递归遍历右子树
- 访问当前结点
非递归实现（双栈法）
利用后序与前序的关系：将前序遍历改为"根→右→左"，结果压入第二个栈，最后依次弹出即为后序序列。
c
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 记录最近访问的结点，用于判断右子树是否已被访问。
c
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)。
考研高频考点
- ⭐ 非递归后序遍历的实现（算法设计题高频，标记法为主要考法）
- ⭐ 根据前序 + 中序 / 后序 + 中序序列还原二叉树（选择题/大题必考）
- ⭐ 后序遍历的应用：表达式树求值、计算树高、释放二叉树（概念题）
- ⭐ 后序序列与前序序列的逆序关系（选择题常考陷阱）
- 后序遍历栈中保存的结点恰好是当前结点到根的路径（可用于求最近公共祖先）
- 三种遍历序列的组合判断树的唯一性（前序+后序不能唯一确定二叉树）
易错：后序遍历的非递归实现是三种遍历中最复杂的，因为需要区分"从左子树返回"还是"从右子树返回"。常见做法是用一个
prev指针记录上次访问的结点，如果上次访问的是当前结点的右孩子，说明右子树已处理完，可以访问当前结点。
易错：后序遍历序列的最后一个元素一定是根结点（类比先序的第一个元素是根）。这个性质在由遍历序列构造二叉树时非常关键。
相关知识
- 前序遍历 —— 后序序列 = 前序（根->右->左）的逆序
- 中序遍历 —— 后序+中序可唯一确定二叉树
- 由遍历序列构造二叉树 —— 后序最后一个元素定根，中序划分左右