后序遍历（Postorder Traversal）
定义
后序遍历是二叉树遍历的一种方式，访问顺序为：左子树 → 右子树 → 根节点。
在递归框架中，后序位置指的是即将离开一个二叉树节点的时候（递归调用之后）。
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
traverse(root.right);
// 后序位置：即将离开节点
System.out.println(root.val);
}
核心特点
- 后序位置能力最强：可以获取参数数据 + 左右子树通过返回值传递的数据
- 后序位置适合处理子树相关问题：因为此时已经知道左右子树的信息
- 归并排序的本质就是二叉树的后序遍历
- 分解问题的思路一般用后序位置：因为需要利用子树返回的结果
为什么后序位置特殊？
| 位置 | 能获取的数据 |
|---|---|
| 前序位置 | 只能从函数参数中获取父节点传递来的数据 |
| 中序位置 | 参数数据 + 左子树返回值 |
| 后序位置 | 参数数据 + 左右子树返回值 |
划重点：一旦遇到和子树有关的问题，大概率要在后序位置写代码，并使用分解问题的思路。
经典应用：二叉树的直径（LeetCode 543）
int maxDiameter = 0;
int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置：利用左右子树深度计算直径
maxDiameter = Math.max(maxDiameter, leftMax + rightMax);
return 1 + Math.max(leftMax, rightMax);
}
后序遍历的两种实现思路
遍历思路（用外部变量）：
int maxDiameter = 0;
void traverse(TreeNode root) {
if (root == null) return;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
traverse(root.left);
traverse(root.right);
}
int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}
// 时间复杂度 O(N²)，每个节点都调用 maxDepth
分解问题思路（推荐，O(N)）：
int maxDiameter = 0;
int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置顺便计算直径
maxDiameter = Math.max(maxDiameter, leftMax + rightMax);
return 1 + Math.max(leftMax, rightMax);
}
// 时间复杂度 O(N)，每个节点只访问一次
与算法框架的联系
归并排序 = 后序遍历
void sort(int[] nums, int lo, int hi) {
if (lo == hi) return;
int mid = (lo + hi) / 2;
sort(nums, lo, mid); // 左子树
sort(nums, mid + 1, hi); // 右子树
// 后序位置：合并两个有序子数组
merge(nums, lo, mid, hi);
}