第21篇-二叉树经典题型-层序遍历-最大深度与路径问题

上一篇我们学习了二叉树的基础知识，重点掌握了前序、中序、后序和层序遍历。

但在真正刷题时，题目通常不会直接问你：

请写一个前序遍历

它更常见的问法是：

• 返回二叉树每一层的节点
• 求二叉树最大深度
• 判断是否存在一条路径和等于目标值
• 找出所有从根节点到叶子节点的路径
• 计算某类路径的数量或最大值

这些题表面不同，但底层都离不开两件事：

遍历节点 + 在遍历过程中维护信息

本篇文章围绕二叉树高频题展开，重点讲三类模型：

学完这篇，你应该能把二叉树题归类为层次、深度、路径三种模型，并写出对应的 Java 模板。

基础准备：二叉树节点定义

本文代码统一使用下面的二叉树节点定义：

public class TreeNode {
int val;
TreeNode left;
TreeNode right;

TreeNode() {
}

TreeNode(int val) {
this.val = val;
}

TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}

很多平台会提前提供 TreeNode，刷题时不一定需要自己写。

题型一：层序遍历为什么是二叉树里的 BFS

层序遍历的意思是：

从上到下，一层一层访问节点

例如下面这棵树：

3
/ \\
9 20
/ \\
15 7

层序遍历结果应该是：

[
[3],
[9, 20],
[15, 7]
]

这其实就是二叉树上的 BFS。

BFS 的核心工具是队列。
在二叉树中，每次从队列取出当前节点，再把它的左右孩子加入队列，就能保证节点按层访问。

层序遍历标准模板

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}

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);
}
}

ans.add(level);
}

return ans;
}
}

为什么一定要记录 size

size 表示当前层有多少个节点。

如果不记录 size，队列在遍历过程中会不断加入下一层节点，当前层和下一层就会混在一起。

关键逻辑是：

int size = queue.size();

for (int i = 0; i < size; i++) {
// 这里只处理当前层节点
}

处理完这 size 个节点，才算完成一整层。

层序遍历就是二叉树上的 BFS，size 用来把不同层拆开。

层序遍历变形：锯齿形层序遍历

有些题会要求第一层从左到右，第二层从右到左，第三层再从左到右。

例如：

3
/ \\
9 20
/ \\
15 7

锯齿形结果是：

[
[3],
[20, 9],
[15, 7]
]

解题思路

仍然使用层序遍历。

区别只是每一层加入结果时，根据方向决定：

• 从左到右：正常追加
• 从右到左：插入到列表头部

Java 代码实现

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root == null) {
return ans;
}

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;

while (!queue.isEmpty()) {
int size = queue.size();
LinkedList<Integer> level = new LinkedList<>();

for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();

if (leftToRight) {
level.addLast(node.val);
} else {
level.addFirst(node.val);
}

if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}

ans.add(new ArrayList<>(level));
leftToRight = !leftToRight;
}

return ans;
}
}

复杂度分析

• 时间复杂度：O(n)，每个节点入队和出队一次
• 空间复杂度：O(n)，队列最多保存一层节点

其中 n 是二叉树节点数量。
锯齿形遍历本质仍然是层序遍历，只是每层收集结果的方向不同。

题型二：最大深度问题

二叉树最大深度是非常经典的递归题。

题目通常是：

给定一棵二叉树，返回它的最大深度。

最大深度指从根节点到最远叶子节点经过的节点数。

例如：

3
/ \\
9 20
/ \\
15 7

最大深度是 3。

解题思路

对于任意一个节点来说：

当前树的最大深度 = max(左子树最大深度, 右子树最大深度) + 1

如果当前节点为空：

空树深度 = 0

这就是典型的后序递归。
因为当前节点的答案依赖左右子树的结果。

Java 代码实现

class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}

int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);

return Math.max(leftDepth, rightDepth) + 1;
}
}

为什么这是后序思想

后序遍历的顺序是：

左子树 -> 右子树 -> 当前节点

最大深度需要先知道左右子树深度，才能算当前节点深度。

所以它的思维过程是：

先问左右孩子要答案，再汇总当前节点答案

最大深度用后序递归最自然，当前节点深度等于左右子树最大深度加一。

最大深度的层序写法

最大深度也可以用层序遍历解决。

思路是：

遍历完一层，深度加一

Java 代码实现

import java.util.LinkedList;
import java.util.Queue;

class Solution {
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;

while (!queue.isEmpty()) {
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);
}
}

depth++;
}

return depth;
}
}

递归写法和层序写法怎么选

刷题时更推荐先掌握递归写法，因为很多二叉树题都可以扩展成“左右子树给当前节点返回信息”。

最小深度：一个容易写错的深度题

最小深度指从根节点到最近叶子节点经过的节点数。

注意，叶子节点必须是：

左右孩子都为空的节点

例如：

1
\\
2

这棵树的最小深度是 2，不是 1。

因为根节点 1 不是叶子节点。

常见错误写法

return Math.min(minDepth(root.left), minDepth(root.right)) + 1;

这段代码在只有一个孩子的情况下会出错。

对于上面的树：

左子树深度 = 0
右子树深度 = 1

错误写法会得到：

min(0, 1) + 1 = 1

但正确答案是 2。

正确 Java 代码

class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}

if (root.left == null && root.right == null) {
return 1;
}

if (root.left == null) {
return minDepth(root.right) + 1;
}

if (root.right == null) {
return minDepth(root.left) + 1;
}

return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}

最小深度必须走到叶子节点，不能把空子树当成一条有效路径。

题型三：路径问题的核心思路

路径问题是二叉树里非常高频的一类题。

常见问法包括：

• 是否存在一条根到叶子的路径，使节点值之和等于目标值
• 返回所有根到叶子的路径
• 返回所有路径和等于目标值的路径
• 统计某种路径数量

这类题的关键是：

递归向下走时维护当前路径的信息

通常需要维护：

• 当前节点
• 当前路径和
• 当前路径列表
• 目标值

路径题最常见的递归结构是：

void dfs(TreeNode root, 当前路径信息) {
if (root == null) {
return;
}

处理当前节点;

if (root 是叶子节点) {
判断是否满足条件;
}

dfs(root.left, 更新后的路径信息);
dfs(root.right, 更新后的路径信息);

撤销当前节点影响;
}

其中“撤销当前节点影响”就是回溯。

路径和一：判断是否存在目标路径

题目：

给定二叉树根节点 root 和目标和 targetSum，判断是否存在从根节点到叶子节点的路径，使路径上所有节点值之和等于 targetSum。

例如：

5
/ \\
4 8
/ / \\
11 13 4
/ \\
7 2

如果 targetSum = 22，存在路径：

5 -> 4 -> 11 -> 2

所以返回 true。

解题思路

每往下走一个节点，就从目标值中减去当前节点值。

当走到叶子节点时，如果剩余目标值等于叶子节点值，说明找到了一条合法路径。

Java 代码实现

class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}

if (root.left == null && root.right == null) {
return root.val == targetSum;
}

int nextTarget = targetSum – root.val;

return hasPathSum(root.left, nextTarget)
|| hasPathSum(root.right, nextTarget);
}
}

为什么只在叶子节点判断

题目要求的是：

从根节点到叶子节点的路径

所以即使中间某个节点的路径和已经等于目标值，也不能直接返回 true。

只有当当前节点是叶子节点时，才说明一条完整路径结束。

路径和题要看清是否要求到叶子节点，只有完整路径满足条件才算成功。

路径和二：返回所有目标路径

上一题只需要判断是否存在路径。
如果题目要求返回所有满足条件的路径，就需要保存路径列表。

题目：

返回所有从根节点到叶子节点，且路径和等于 targetSum 的路径。

解题思路

递归过程中维护一个 path：

第 4 步就是回溯，否则会影响其他分支。

Java 代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
dfs(root, targetSum, path, ans);
return ans;
}

private void dfs(
TreeNode root,
int targetSum,
List<Integer> path,
List<List<Integer>> ans) {
if (root == null) {
return;
}

path.add(root.val);

if (root.left == null && root.right == null && root.val == targetSum) {
ans.add(new ArrayList<>(path));
}

int nextTarget = targetSum – root.val;
dfs(root.left, nextTarget, path, ans);
dfs(root.right, nextTarget, path, ans);

path.remove(path.size() – 1);
}
}

为什么加入答案时要复制 path

错误写法：

ans.add(path);

这样加入的是同一个列表引用。

后续递归回溯时，path 会继续变化，答案中的内容也会被一起改掉。

正确写法是：

ans.add(new ArrayList<>(path));

这样保存的是当前路径的一份快照。

保存路径时要回溯，加入答案时要复制，避免不同分支互相污染。

二叉树所有路径：字符串路径问题

还有一类路径题要求返回从根节点到叶子节点的字符串路径。

例如：

1
/ \\
2 3
\\
5

返回：

["1->2->5", "1->3"]

Java 代码实现

import java.util.ArrayList;
import java.util.List;

class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> ans = new ArrayList<>();
if (root == null) {
return ans;
}

dfs(root, "", ans);
return ans;
}

private void dfs(TreeNode root, String path, List<String> ans) {
if (root == null) {
return;
}

String curPath;
if (path.length() == 0) {
curPath = String.valueOf(root.val);
} else {
curPath = path + "->" + root.val;
}

if (root.left == null && root.right == null) {
ans.add(curPath);
return;
}

dfs(root.left, curPath, ans);
dfs(root.right, curPath, ans);
}
}

字符串路径和列表路径的区别

字符串是不可变对象。
每次拼接都会生成新的字符串，所以这里不需要手动回溯。

但列表 path 是可变对象。
如果多个递归分支共用同一个列表，就必须在递归结束后撤销选择。

路径问题模板总结

路径题可以按下面的问题来拆：

判断存在性模板

boolean dfs(TreeNode root, int target) {
if (root == null) {
return false;
}

if (root.left == null && root.right == null) {
return root.val == target;
}

return dfs(root.left, target – root.val)
|| dfs(root.right, target – root.val);
}

返回所有路径模板

void dfs(TreeNode root, List<Integer> path, List<List<Integer>> ans) {
if (root == null) {
return;
}

path.add(root.val);

if (root.left == null && root.right == null) {
ans.add(new ArrayList<>(path));
}

dfs(root.left, path, ans);
dfs(root.right, path, ans);

path.remove(path.size() – 1);
}

路径题本质是 DFS 加状态维护，判断类题返回布尔值，收集类题要注意回溯和复制。

常见坑点：二叉树经典题最容易错在哪里

1. 空树没有处理

二叉树题几乎都要先判断：

if (root == null) {
return ...;
}

返回值根据题目决定：

• 返回列表：通常返回空列表
• 返回深度：返回 0
• 判断是否存在路径：返回 false

2. 混淆节点数和边数

最大深度通常按节点数计算。

例如只有一个根节点：

1

最大深度是 1。

但有些图论题会按边数计算距离。
刷题时要看清题目定义。

3. 最小深度把空子树当路径

最小深度必须到叶子节点。
如果一个节点只有右子树，不能取左子树深度 0 作为答案。

4. 路径和没有判断叶子节点

路径和题如果要求根到叶子，就必须写：

root.left == null && root.right == null

中间节点即使路径和满足目标，也不能直接返回成功。

5. 返回所有路径时忘记回溯

使用 List<Integer> path 时，递归结束必须撤销：

path.remove(path.size() – 1);

否则其他分支会带着错误路径继续搜索。

6. 加入答案时没有复制路径

应该写：

ans.add(new ArrayList<>(path));

不要直接写：

ans.add(path);

直接加入原列表会导致答案被后续回溯修改。

复杂度分析：二叉树经典题的统一成本

对于层序遍历、最大深度、路径和这类题，通常都会访问每个节点一次。

所以时间复杂度一般是：

O(n)

其中 n 是二叉树节点数量。

空间复杂度要看使用方式：

在最坏情况下，树退化成链表，h = n。
如果是完全二叉树，某一层节点数量可能接近 n / 2，BFS 队列空间也是 O(n)。

模板总结：三类高频题怎么选方法

可以简单记成：

按层用队列，求深度问子树，找路径做回溯

总结

二叉树题看起来变化很多，但常见基础题大多可以归到三类模型。

你可以重点记住下面几句话：

• 层序遍历是二叉树上的 BFS
• 队列负责按顺序访问节点
• size 用来区分当前层和下一层
• 最大深度适合用后序递归
• 当前节点高度来自左右子树高度
• 最小深度必须走到叶子节点
• 路径和题要看清是否要求根到叶子
• 返回所有路径时要回溯
• 加入答案时要复制当前路径
• 二叉树题的本质是遍历过程中维护信息