二叉树系列算法核心纲领
本文是 labuladong 算法体系的二叉树总纲，浓缩了所有二叉树题目的解题框架
核心思想
二叉树解题只有两种思维模式：
- 遍历思路：通过
traverse函数 + 外部变量，遍历一遍二叉树得到答案 - 分解问题思路：定义递归函数，通过子问题（子树）的答案推导出原问题的答案
关键问题：单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？
前中后序位置的深入理解
前中后序不是三种顺序不同的 List，而是遍历二叉树过程中处理每一个节点的三个特殊时间点：
- 前序位置：刚进入一个节点的时候（递归之前）
- 中序位置：左子树都遍历完，即将开始遍历右子树的时候
- 后序位置：即将离开一个节点的时候（递归之后）
为什么多叉树没有中序遍历？ 因为二叉树每个节点只有唯一一次左子树切换右子树，而多叉树节点可能有多个子节点，会多次切换子树。
后序位置的特殊性
前中后序位置的代码能力依次增强：
| 位置 | 能获取的数据 |
|---|---|
| 前序位置 | 只能从函数参数中获取父节点传递来的数据 |
| 中序位置 | 参数数据 + 左子树通过返回值传递的数据 |
| 后序位置 | 参数数据 + 左右子树通过返回值传递的数据 |
划重点：一旦遇到和子树有关的问题，大概率要在后序位置写代码，并使用分解问题的思路。
实例：二叉树的直径（LeetCode 543）
错误思路：在每个节点调用 maxDepth 计算左右子树深度 → 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);
}
两种思路的代码对比
示例：二叉树的最大深度（LeetCode 104）
遍历思路（traverse + 外部变量）：
int depth = 0, res = 0;
void traverse(TreeNode root) {
if (root == null) return;
depth++; // 前序位置：进入节点
if (root.left == null && root.right == null) {
res = Math.max(res, depth);
}
traverse(root.left);
traverse(root.right);
depth--; // 后序位置：离开节点
}
分解问题思路（递归函数返回值）：
int maxDepth(TreeNode root) {
if (root == null) return 0;
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置：利用子树结果推导原问题
return 1 + Math.max(leftMax, rightMax);
}
前序遍历的两种实现
遍历思路（常规）：
List<Integer> res = new LinkedList<>();
void traverse(TreeNode root) {
if (root == null) return;
res.add(root.val); // 前序位置
traverse(root.left);
traverse(root.right);
}
分解问题思路（不常见但巧妙）：
List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (root == null) return res;
res.add(root.val);
res.addAll(preorderTraversal(root.left));
res.addAll(preorderTraversal(root.right));
return res;
}
注：第二种方法在 Java 中时间复杂度可能达到 O(N²)，除非实现 O(1) 的 addAll。
二叉树与高级算法的联系
快速排序 = 二叉树的前序遍历
void sort(int[] nums, int lo, int hi) {
if (lo >= hi) return;
// 前序位置：构造分界点
int p = partition(nums, lo, hi);
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}
归并排序 = 二叉树的后序遍历
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);
}
三种算法的本质区别
| 算法 | 对应二叉树思路 | 关注点 |
|---|---|---|
| 动态规划 | 分解问题（分治） | 整棵「子树」 |
| 回溯算法 | 遍历思路 | 节点间的「树枝」 |
| DFS 算法 | 遍历思路 | 单个「节点」 |
代码体现：
- 回溯算法：做选择/撤销选择在 for 循环里面
- DFS 算法：做选择/撤销选择在 for 循环外面
层序遍历框架
void levelTraverse(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int sz = q.size();
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 处理当前节点
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
}
}
层序遍历是 BFS 算法的基础，常用于求无权图的最短路径。
相关概念
- 二叉树：所有递归算法的基础数据结构
- 前序遍历：刚进入节点时的处理时机
- 中序遍历：BST 中序遍历结果有序
- 后序遍历：能获取左右子树信息的特殊位置
- 层序遍历：BFS 框架基础
- DFS：深度优先搜索，关注单个节点
- BFS：广度优先搜索，关注层级扩散
- 动态规划：分解问题思路的体现
- 回溯算法：遍历思路的体现（关注树枝）
- 快速排序：二叉树前序遍历的应用
- 归并排序：二叉树后序遍历的应用
相关题目
| LeetCode | 力扣 | 说明 |
|---|---|---|
| 104. Maximum Depth of Binary Tree | 104. 二叉树的最大深度 | 两种思路对比 |
| 144. Binary Tree Preorder Traversal | 144. 二叉树的前序遍历 | 两种思路对比 |
| 543. Diameter of Binary Tree | 543. 二叉树的直径 | 后序位置应用 |
前置知识
- 二叉树基础及常见类型：二叉树类型与术语
- 二叉树遍历基础：递归遍历与层序遍历详解
- 算法总结：框架思维与代码模板