深搜（DFS）& 广搜（BFS）_树的深搜和广搜

搜索的核心概念

问题求解树

是一种思维逻辑层面的结构，而非程序中的实际存储结构；思维结构可以表示无限的概念

设计搜索算法的核心关键点

设计问题求解树的状态

搜索剪枝和优化

在问题求解树搜索过程中，对于某些分支或子树通过某些条件的筛选不进行搜索。

搜索方法

对问题求解树不同的遍历方式

深度遍历 - Depth First Search

程序实现 =》 递归

广度遍历 - Breadth First Search

层序遍历 =》 队列
适合场景：求解最优化问题

练习

来自Leetcode
下面这个题目即可使用深搜又可使用广搜，理解下两种方法解题

993. 二叉树的堂兄弟节点

在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。

示例 1：

输入：root = [1,2,3,4], x = 4, y = 3
输出：false

示例 2：

输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true

方法一： 深搜 dfs

思路：

• 问题状态：被查找元素 & 当前节点 & 父节点 & 当前节点层深
• 递归函数设计：
  • 入参： 当前节点 & 父节点
  • 返回值： 当前节点层深
  • 逻辑：结束条件 =》 当前节点为待查找元素 返回0， 当前节点为null, 返回-1（特殊值）
    状态扩展 =》 当前节点的左（右）子节点，父节点值重新置为当前节点值

/**
 * Definition for a binary tree node.
 * 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;
 *     }
 * }
 */
class Solution {
    private int dfs(TreeNode root, int val, TreeNode father) {
        if (root == null) return -1;
        if (root.val == val) return 0;
        father.val = root.val;
        int level;
        level = dfs(root.left, val, father);
        if (level != -1) return level + 1;
        father.val = root.val;
        level = dfs(root.right, val, father);
        if (level != -1) return level + 1;
        return -1;
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        int l_x, l_y;
        TreeNode father_x = new TreeNode(-1), father_y = new TreeNode(-1);
        l_x = dfs(root, x, father_x);
        l_y = dfs(root, y, father_y);
        return l_x == l_y && father_x.val != father_y.val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

方法二： 广搜 bfs

问题状态： 当前节点 & 父节点 & 当前节点层深

class Solution {
    class Node {
        TreeNode curr;
        TreeNode father;
        int level;

        public Node(TreeNode curr, TreeNode father, int level) {
            this.curr = curr;
            this.father = father;
            this.level = level;
        }
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        int level_x = -1, level_y = -1;
        TreeNode father_x = new TreeNode(-1), father_y = new TreeNode(-1);
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(root, null, 0));
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node.curr.val == x) {//终止条件：判断是否为带查找元素
                level_x = node.level;
                father_x = node.father;
            }
            if (node.curr.val == y) {//终止条件：判断是否为带查找元素
                level_y = node.level;
                father_y = node.father;
            }
            if (node.curr.left != null) {//扩展状态【搜索树左右子树】
                queue.offer(new Node(node.curr.left, node.curr, node.level + 1));
            }
            if (node.curr.right != null) {//扩展状态【搜索树左右子树】
                queue.offer(new Node(node.curr.right, node.curr, node.level + 1));
            }
        }
        return level_x == level_y && father_x.val != father_y.val;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

1091. 二进制矩阵中的最短路径

给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。

二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：

路径途经的所有单元格都的值都是 0 。
路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
畅通路径的长度 是该路径途经的单元格总数。

示例 1：

输入：grid = [[0,1],[1,0]]
输出：2
示例 2：

输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4

感觉这个题目就是广搜的比较又代表性的题目，其他的题目都是大同小异，可以深入理解下
问题状态：当前元素【一维坐标 & 二维坐标 & 距离起点距离】

class Solution {
    int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}};

    public int shortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] != 0) return -1;//当矩阵左上角的第一个元素不为0， 则说明无法开始站在起始位置
        int n = grid.length;
        int m = grid[0].length;
        int[][] visit = new int[n][m];//存储原矩阵相应位置是否被访问过，用于剪枝
        visit[0][0] = 1;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 1});
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            if (curr[0] == n - 1 && curr[1] == n - 1) {//是否满足搜索终止条件 （走到终点）
                return curr[2];
            }
            for (int i = 0; i < dir.length; i++) {//扩展状态【二维矩阵方向数组dir】
                int x = curr[0] + dir[i][0];
                int y = curr[1] + dir[i][1];
                if (x < 0 || x >= n) continue;//剪枝 （下标越界）
                if (y < 0 || y >= m) continue;//剪枝 （下标越界）
                if (grid[x][y] != 0) continue;//剪枝 （题目要求）
                if (visit[x][y] != 0) continue;//剪枝 （重复访问）
                visit[x][y] = curr[2] + 1;
                queue.offer(new int[]{x, y, visit[x][y]});
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

130. 被围绕的区域(dfs地图搜索)

给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例 1：

分析：
四个边上的O没有被X围绕 =》由这些O向内扩展的所有可达的O均没有被X围绕； 由这些O向内扩展的所有不可达的O均被X围绕
问题状态：当前元素【一维坐标 & 二维坐标 & 是否为O且从四个边的O出发可达】
递归函数设计：

• 入参：矩阵横坐标 & 矩阵纵坐标 & 原数组
• 返回值： void
  • 逻辑：进入该递归函数的前提：矩阵中横纵坐标位置处元素为"O"且被访问到，将该元素update为小写"o";
  • 状态扩展 =》 在该递归函数内部进行状态扩展【矩阵方向数组】：剪枝 + 递归调用

class Solution {
    private int n;
    private int m;

    int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    private void dfs(int i, int j, char[][] board) {
        board[i][j] = 'o';
        for (int k = 0; k < dir.length; k++) {
            int x = i + dir[k][0];
            int y = j + dir[k][1];
            if (x < 0 || x >= n) continue;
            if (y < 0 || y >= m) continue;
            if (board[x][y] != 'O') continue;
            dfs(x, y, board);
        }
    }

    public void solve(char[][] board) {
        n = board.length;
        m = board[0].length;
        for (int i = 0; i < n; i++) {
            if (board[i][0] == 'O') dfs(i, 0, board);
            if (board[i][m - 1] == 'O') dfs(i, m - 1, board);
        }
        for (int j = 0; j < m; j++) {
            if (board[0][j] == 'O') dfs(0, j, board);
            if (board[n - 1][j] == 'O') dfs(n - 1, j, board);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == 'o') {
                    board[i][j] = 'O';
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

[473. 火柴拼正方形] (dfs)

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

分析：题目可以转化为：所拥有的火柴是否可以平均分为四组？

​ 初始化一个大小为4的一维数组(4个桶)，每个元素初始化为火柴总长度/4（桶的容量）;

​ 桶的容量为火柴总长度/4, 当将所有火柴都放入桶中时，代表4个桶均放满
问题状态： 第ind根火柴 & 桶的剩余容量 int[] arr
递归函数：

• 入参：ind & int[]arr & 原数组int[] matchsticks
• 返回值：题目所求“是否能用所有的火柴拼成正方形” boolean
• 逻辑：
  • 满足结束条件， 当遍历到了所有火柴，说明可以将所有火柴都放入桶中，因为桶的总容量为火柴长度之和。即：火柴可以平均分为4组
  • 状态扩展： 剪枝 【当前桶的剩余容量放不下当前火柴 或者 当前桶的容量放不下当前火柴与剩余最短的火柴】
    递归调用【更新桶剩余容量】

class Solution {
    private boolean dfs(int ind, int[] arr, int[] matchsticks) {
        if (ind == -1) return true;//当ind 超限时，说明所有的火柴都放到桶中，且均放满
        for (int i = 0; i < arr.length; i++) {//遍历4个桶
            if (arr[i] < matchsticks[ind]) continue;//桶的容量不够火柴长度
            if (arr[i] == matchsticks[ind] || arr[i] >= matchsticks[ind] + matchsticks[0]) {
                arr[i] -= matchsticks[ind];//更新桶的剩余容量
                if (dfs(ind - 1, arr, matchsticks)) return true;
                arr[i] += matchsticks[ind];//若当前火柴放入当前桶后没有找到解，则需要将火柴从当前桶中拿出
            }
        }
        return false;
    }

    public boolean makesquare(int[] matchsticks) {
        Arrays.sort(matchsticks);
        int sum = 0;
        for (int matchstick : matchsticks) {
            sum += matchstick;
        }
        if (sum % 4 != 0) return false;
        int[] arr = new int[4];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sum / 4;
        }
        return dfs(matchsticks.length - 1, arr, matchsticks);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28