二叉树后序遍历（Postorder Traversal）

算法原理

后序遍历的口诀是**「左右根」**：先递归遍历左子树，再递归遍历右子树，两边都回来之后最后记录当前根。它是三种 DFS 里"根"出场最晚的一种——节点要等自己的整棵左子树和整棵右子树都被处理完，才轮到它被记录。

本动画用同一棵 7 节点的完全二叉搜索树演示（默认 2s/拍，全片 22 拍）：

树：根 5（左子 3，右子 8）；3 的孩子 1、4；8 的孩子 7、9
后序输出：1 4 3 7 9 8 5
节拍：宣告 1 + 进入 7 + 访问 7 + 返回 6 + 完成 1

看点在**"根最后落字"：输出条的前 6 格全是两棵子树的节点，根 5 压轴在最后一格才出现——而且输出序列的最后一个元素永远是整棵树的根**。叶子先记、越往上越晚，整条输出是一张"自底向上"的顺序表。

动画怎么看

• 上半区是树：7 个节点盒 + 父子实线连线；黄色描边 = 遍历者焦点，逐拍移动，本拍移动的边青色加粗；访问过的节点转绿色常驻；
• 进入拍：焦点落到新节点，状态行显示 进入 v · 暂不记录——先序在这一拍就记了，后序必须等；
• 访问拍：焦点第二次（也是最后一次）落在该节点、左右都回来的那拍，输出条才写入它的值；
• 返回拍：状态行 返回 p · 查完 n，带着"孩子都处理完了"的语义向上移动；
• 口诀立牌：左上角常驻「口诀 左右根」；完成后大✓，✓ 完成 ｜ 后序遍历 7 节点全部输出。

复杂度分析

C++ 参考代码

#include <iostream>
struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void postorder(Node *root) {
    if (!root) return;
    postorder(root->left);           // 左：左子树全部处理完
    postorder(root->right);          // 右：右子树也处理完
    std::cout << root->val << " ";   // 根：最后才记录
}

int subtreeSum(Node *root) {         // 后序的典型用途：先算完两棵子树
    if (!root) return 0;
    return subtreeSum(root->left) + subtreeSum(root->right) + root->val;
}

int main() {
    // 完全 BST：5(3(1,4), 8(7,9))
    Node a(1), b(4), c(3), d(7), e(9), f(8), root(5);
    c.left = &a; c.right = &b;
    f.left = &d; f.right = &e;
    root.left = &c; root.right = &f;
    postorder(&root);                // 输出 1 4 3 7 9 8 5
    return 0;
}

什么时候用后序遍历

凡是**"孩子没算完就不能算父亲"的场合，都是后序的主场：删除整棵树（必须先删孩子再删父亲，否则悬空指针）、目录/文件大小汇总（文件夹大小 = 子项之和，自底向上累加）、表达式树求值（先算两个操作数才能做运算，对应后缀表达式 / 逆波兰式）、树形 DP（父节点的状态由子节点状态推出）、以及根据两个遍历序列重建树**（后序末位定根）。判断依据一句话：需要拿子问题的结果往上交，就用后序——动画里根 5 永远最后一个落字，就是这个道理。