2026/4/18大约 14 分钟算法二叉树DFSBFS递归LeetCode
二叉树遍历与递归
二叉树是面试中频率最高的数据结构之一，几乎所有题目都围绕递归思维展开。本文用 Mermaid 图和步骤可视化，让你真正理解"树上的递归"是如何运转的。
一、二叉树结构可视化
1.1 示例树（本文贯穿使用）
1.2 颜色约定
蓝色 = 根节点 / 当前访问
紫色 = 第2层
绿色 = 第3层
橙色 = 叶子节点
红色 = 关键路径节点
1.3 Java 节点定义
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}二、三种 DFS 遍历
2.1 遍历顺序对比
| 遍历方式 | 访问顺序 | 示例树结果 |
|---|---|---|
| 前序（Pre-order） | 根 → 左 → 右 | 1,2,4,8,9,5,3,6,7 |
| 中序（In-order） | 左 → 根 → 右 | 8,4,9,2,5,1,6,3,7 |
| 后序（Post-order） | 左 → 右 → 根 | 8,9,4,5,2,6,7,3,1 |
2.2 前序遍历——递归调用栈演示
2.3 中序遍历——递归调用栈演示
2.4 三种遍历 Java 代码
// 前序遍历
public void preorder(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val); // 先访问根
preorder(root.left, res); // 再左子树
preorder(root.right, res);// 再右子树
}
// 中序遍历
public void inorder(TreeNode root, List<Integer> res) {
if (root == null) return;
inorder(root.left, res); // 先左子树
res.add(root.val); // 再访问根
inorder(root.right, res); // 再右子树
}
// 后序遍历
public void postorder(TreeNode root, List<Integer> res) {
if (root == null) return;
postorder(root.left, res); // 先左子树
postorder(root.right, res); // 再右子树
res.add(root.val); // 最后访问根
}口诀： "根" 的位置决定遍历名字——前=根最先，中=根居中，后=根最后。
三、BFS 层序遍历
层序遍历用队列实现，每次处理一整层节点，天然适合"按层"类题目。
3.1 层序遍历步骤可视化
初始 (层0)
队列：[1] 已输出：[]
1
当前处理层
第1层
出队 1，输出 [1]，将子节点 2、3 入队
2
3
队列：[2, 3]
已输出：[[1]]
第2层
出队 2、3，输出 [2,3]，将子节点 4、5、6、7 入队
4
5
6
7
队列：[4, 5, 6, 7]
已输出：[[1], [2,3]]
第3层（叶子）
出队 4、5、6、7，输出 [4,5,6,7]，叶子节点无子节点入队
4
5
6
7
队列已空，BFS 结束
最终输出：[[1], [2,3], [4,5,6,7]]
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size(); // 当前层节点数
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
res.add(level);
}
return res;
}四、LeetCode 精选题
LC 104 — 二叉树最大深度
题目： 给定一棵二叉树，返回其最大深度。
两种解法
DFS 递归
思路： 最大深度 = 1 + max(左子树深度, 右子树深度)
public int maxDepth(TreeNode root) {
if (root == null) return 0;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}BFS 层序
思路： 层序遍历，统计总层数即为最大深度。
public int maxDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
depth++;
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return depth;
}复杂度： 时间 O(n)，空间 O(h)（DFS 递归栈深度 h = 树高）/ O(n)（BFS 队列）
LC 102 — 二叉树层序遍历
题目： 返回二叉树的层序遍历结果，每层节点值为一个子数组。
代码与上文"BFS 层序遍历"一节完全一致，不再重复。
层序遍历可视化输出：
层0
1
层1
2
3
层2
4
5
6
7
层3
8
9
LC 236 — 二叉树的最近公共祖先
题目： 给定树中两个节点 p、q，找到它们的最近公共祖先（LCA）。
LCA Mermaid 树图（查找节点 8 和 5 的 LCA）
节点 8（绿色）和节点 5（橙色）的 LCA 是节点 2（红色）。
递归思路
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 递归终止：遇到 null 或找到目标节点
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// 左右都有返回值，说明 p、q 分属两侧，当前 root 即为 LCA
if (left != null && right != null) return root;
// 否则返回非 null 的那侧（p、q 在同一子树中）
return (left != null) ? left : right;
}关键理解： 后序递归——先处理子树，再用子树结果决策当前节点。
LC 543 — 二叉树的直径
题目： 求二叉树中任意两节点路径长度的最大值（不必经过根节点）。
图解
最长路径为 4 → 2 → 5，长度为 3（红色路径）。
思路： 对每个节点，直径 = 左子树高度 + 右子树高度。用全局变量记录最大值。
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return maxDiameter;
}
private int depth(TreeNode node) {
if (node == null) return 0;
int leftDepth = depth(node.left);
int rightDepth = depth(node.right);
// 经过当前节点的路径长度 = 左深 + 右深
maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
// 返回当前节点的深度（选较长的一侧 +1）
return 1 + Math.max(leftDepth, rightDepth);
}LC 124 — 二叉树中的最大路径和（进阶）
题目： 路径中每个节点只能出现一次，路径可以不经过根节点，求路径中节点值的最大和。
路径标注
最大路径为 15 → 20 → 7，路径和 = 42（红色节点）。
算法思路
每个节点可以作为"路径的最高点"（左贡献 + 节点值 + 右贡献），但向上返回时只能选择一侧（保持路径连通性）。
- 贡献值 = max(0, max(左贡献, 右贡献)) + 当前节点值
（取 max 0 是因为负贡献不如不选） - 更新答案 = 左贡献 + 节点值 + 右贡献
Java 代码
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
gain(root);
return maxSum;
}
private int gain(TreeNode node) {
if (node == null) return 0;
// 负贡献直接丢弃（取 0）
int leftGain = Math.max(gain(node.left), 0);
int rightGain = Math.max(gain(node.right), 0);
// 经过当前节点的路径和
maxSum = Math.max(maxSum, node.val + leftGain + rightGain);
// 向父节点只能提供一侧的贡献
return node.val + Math.max(leftGain, rightGain);
}LC 105 — 从前序与中序遍历序列构造二叉树
题目： 给定前序遍历 preorder 和中序遍历 inorder，还原二叉树。
分治图解
分析
preorder[0]始终是当前子树的根节点- 在
inorder中找到根节点位置idx inorder[0..idx-1]是左子树，inorder[idx+1..]是右子树- 根据左子树长度切割
preorder，递归构建
Java 代码
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
indexMap.put(inorder[i], i);
}
return build(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1, indexMap);
}
private TreeNode build(int[] pre, int preL, int preR,
int[] in, int inL, int inR,
Map<Integer, Integer> indexMap) {
if (preL > preR) return null;
int rootVal = pre[preL];
TreeNode root = new TreeNode(rootVal);
int idx = indexMap.get(rootVal); // 在中序中的位置
int leftSize = idx - inL; // 左子树节点数
root.left = build(pre, preL + 1, preL + leftSize,
in, inL, idx - 1, indexMap);
root.right = build(pre, preL + leftSize + 1, preR,
in, idx + 1, inR, indexMap);
return root;
}五、二叉搜索树（BST）
5.1 BST 核心特性
BST 性质：
- 左子树所有节点值 < 根节点值
- 右子树所有节点值 > 根节点值
- 中序遍历结果为严格升序序列
5.2 BST 查找、插入、删除
// 查找
public TreeNode search(TreeNode root, int val) {
if (root == null || root.val == val) return root;
return val < root.val ? search(root.left, val) : search(root.right, val);
}
// 插入
public TreeNode insert(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) root.left = insert(root.left, val);
else if (val > root.val) root.right = insert(root.right, val);
return root;
}
// 删除（三种情况）
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
// 情况1：叶子节点，直接删
if (root.left == null && root.right == null) return null;
// 情况2：只有一个子节点
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 情况3：有两个子节点，用右子树最小值（中序后继）替代
TreeNode minNode = getMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
}
return root;
}
private TreeNode getMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}5.3 LC 98 — 验证二叉搜索树
关键思路： 不能仅比较父子关系，需要传递上下界。
错误直觉
// 错误！只比较父子，会漏掉跨层约束
// 例如下面的树满足父子关系，但不是 BST：
// 5
// / \
// 1 4
// / \
// 3 6
// 4 < 5（正确），但 3 < 5（根）违反了右子树全大于根的约束正确解法
public boolean isValidBST(TreeNode root) {
return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
}
private boolean validate(TreeNode node, long min, long max) {
if (node == null) return true;
if (node.val <= min || node.val >= max) return false;
return validate(node.left, min, node.val) // 左子树上界收紧为当前值
&& validate(node.right, node.val, max); // 右子树下界收紧为当前值
}5.4 LC 230 — BST 中第 K 小的元素
思路： BST 中序遍历即为升序，找第 K 个输出即可。
中序遍历过程
Java 代码
int count = 0, result = 0;
public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return result;
}
private void inorder(TreeNode node, int k) {
if (node == null) return;
inorder(node.left, k);
count++;
if (count == k) {
result = node.val;
return;
}
inorder(node.right, k);
}六、递归思维总结
解题框架
// 二叉树通用递归模板
ReturnType solve(TreeNode root) {
// 1. 递归终止条件
if (root == null) return baseCase;
// 2. 递归处理左右子树
ReturnType left = solve(root.left);
ReturnType right = solve(root.right);
// 3. 当前节点的处理逻辑
return combine(root.val, left, right);
}常见题型归纳
| 题型 | 遍历方式 | 典型题 |
|---|---|---|
| 统计/求最值 | 后序（先拿子树结果） | LC 104 最大深度、LC 543 直径 |
| 路径问题 | 后序 + 全局变量 | LC 124 最大路径和 |
| 查找/验证 | 前序（先判当前节点） | LC 98 验证BST、LC 236 LCA |
| 构造树 | 前序（先建根节点） | LC 105 重建二叉树 |
| 层次属性 | BFS | LC 102 层序遍历、LC 104 DFS版 |
核心心法： 明确递归函数的返回值语义——函数返回什么？调用者如何利用返回值？想清楚这两点，递归便水到渠成。
想要更系统的算法提升？
如果你觉得本文有帮助，欢迎关注我的知识星球，里面有：
- 300+ 道 LeetCode 题解（含图解 + 多语言代码）
- 大厂面试真题汇总与解析：字节、腾讯、阿里、美团真题精讲
- 每周直播算法讲解，直播答疑互动
- 专属刷题打卡群，和数百名同学一起坚持
扫码加入，一起攻克算法面试！