蓝桥杯 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++;// 从当前岛屿的陆地开始DFSdfs(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"]}
}