蓝桥杯 Java B 组之岛屿数量、二叉树路径和（区分DFS与回溯）
Day 3：岛屿数量、二叉树路径和（区分DFS与回溯）
📖 一、深度优先搜索（DFS）简介
深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。它会沿着树的分支向下深入，直到节点无法继续深入为止（即叶子节点），然后返回并访问未遍历的分支。
DFS的典型应用场景包括：
- 图的遍历：搜索图中的连通区域。
- 树的遍历：包括前序、中序、后序遍历。
- 岛屿数量问题：在二维网格中查找连通的区域。
- 路径问题：寻找路径和进行条件限制。
DFS通常使用递归实现，也可以使用栈来模拟递归过程。
DFS与回溯的区别：
- DFS：DFS侧重于遍历或搜索所有可能的路径。它没有特定的“回溯”条件，而是遍历完一个分支后直接回退，直到找到其他未访问的节点。
- 回溯：回溯通常用于寻找“所有解”，即我们在遍历某一路径时，如果发现该路径无法继续时会“回退”并尝试其他路径。回溯是一种基于试探的搜索。
简而言之：回溯是一种DFS的应用，当我们通过DFS遍历所有路径时，如果某一路径不满足条件，我们需要回退并尝试其他路径。
📖 二、岛屿数量问题
问题描述： 给定一个由 '1'（陆地）和 '0'（水域）组成的二维网格，计算网格中岛屿的数量。岛屿是由一组相邻的 '1'（陆地）组成的，水平或垂直方向上相邻的陆地算作一个岛屿。
思路与分析：
- 我们可以使用DFS来遍历所有陆地块，并在遍历的过程中标记已经访问过的陆地。
- 遍历二维数组中的每个点，如果是陆地 ('1')，就从这个点开始执行DFS，标记与其相连的所有陆地为已访问。
- 每次启动DFS时，我们会遇到一个新的岛屿，因此岛屿数量加1。
DFS的递归实现：
- 对于每个陆地点（'1'），启动DFS，将与它相连的所有陆地都标记为访问过（可以改为'0'或者使用一个visited数组）。
- 每次DFS的调用都从当前陆地开始，探索四个方向（上下左右），并继续递归。
代码实现（岛屿数量）：
public class IslandCount {
// 方向数组，用于上下左右遍历
private static final int[] DIRS = {-1, 0, 1, 0, -1, 0};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return 0;
}
int rows = grid.length;
int cols = grid[0].length;
int islandCount = 0;
// 遍历整个网格
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 找到一个陆地'1'，则触发DFS进行标记
if (grid[i][j] == '1') {
islandCount++;
// 从当前岛屿的陆地开始DFS
dfs(grid, i, j, rows, cols);
}
}
}
return islandCount;
}
// 深度优先搜索（DFS）
private void dfs(char[][] grid, int i, int j, int rows, int cols) {
// 如果越界或当前位置是水域（'0'），返回
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
return;
}
// 标记当前陆地为水域
grid[i][j] = '0';
// 递归检查四个方向（上下左右）
for (int d = 0; d < 4; d++) {
int newI = i + DIRS[d];
int newJ = j + DIRS[d + 1];
dfs(grid, newI, newJ, rows, cols);
}
}
public static void main(String[] args) {
IslandCount ic = new IslandCount();
char[][] grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '1', '1'},
{'0', '0', '1', '1', '0'}
};
System.out.println(ic.numIslands(grid)); // 输出 3
}
}
代码讲解：
- DFS方法：
dfs(grid, i, j, rows, cols)，从当前点（i, j）开始，遍历四个方向，递归地标记所有连通的陆地为水域（'0'），避免重复计数。 - 主方法：
numIslands，遍历整个网格，每遇到一个'1'，就触发DFS，增加岛屿计数。
时间复杂度：
- O(m * n)，其中
m是网格的行数，n是网格的列数。每个格子最多访问一次。
📖 三、二叉树路径和问题
问题描述： 给定一个二叉树，求从根到叶子节点的所有路径和。返回所有路径和的总和。
思路与分析：
- 使用DFS遍历二叉树的每个节点，并计算路径和。
- 每到一个叶子节点，就将当前路径和添加到结果列表中。
- 在DFS过程中，我们不断传递当前路径和，直到叶子节点。
DFS的递归实现：
- 在每个节点，计算当前路径和（当前路径和 = 上一个路径和 + 当前节点值）。
- 递归地访问左右子树，直到叶子节点。
- 遇到叶子节点时，将路径和加入到结果集。
代码实现（二叉树路径和）：
import java.util.*;
public class BinaryTreePathSum {
// 二叉树节点定义
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public List<String> binaryTreePaths(TreeNode root) {
List<String> result = new ArrayList<>();
if (root != null) {
dfs(root, "", result);
}
return result;
}
// DFS方法
private void dfs(TreeNode node, String path, List<String> result) {
// 叶子节点，路径加上当前节点的值，添加到结果集
if (node.left == null && node.right == null) {
result.add(path + node.val);
return;
}
// 递归访问左右子树
if (node.left != null) {
dfs(node.left, path + node.val + "->", result);
}
if (node.right != null) {
dfs(node.right, path + node.val + "->", result);
}
}
public static void main(String[] args) {
// 构造一个简单的二叉树
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.right = new TreeNode(5);
BinaryTreePathSum solution = new BinaryTreePathSum();
System.out.println(solution.binaryTreePaths(root)); // 输出 ["1->2->5", "1->3"]
}
}
代码讲解：
- DFS方法：
dfs(node, path, result)，从当前节点开始，构建路径。如果当前节点是叶子节点，保存路径。如果不是叶子节点，则递归访问左右子树。 - 路径拼接：路径通过字符串拼接来构建，格式为
root->left->right。
时间复杂度：
- O(n)，其中
n是二叉树的节点数。每个节点都会被访问一次。