回溯+DFS+BFS_多叉树和回溯树的区别

回溯和DFS的区别

1. DFS是一种算法结构，回溯是一种算法思想。
2. 回溯就是通过不同的尝试来生成问题的解，有点类似于穷举，但是和穷举不同的是回溯会“剪枝”。剪枝的意思也就是说对已经知道错误的结果没必要再枚举接下来的答案了，比如一个有序数列1,2,3,4,5，我要找和为5的所有集合，从前往后搜索我选了1，然后2，然后选3的时候发现和已经大于预期，那么4,5肯定也不行，这就是一种对搜索过程的优化。
3. 回溯搜索是深度优先搜索（DFS）的一种。对于某一个搜索树来说（搜索树是起记录路径和状态判断的作用），回溯和DFS，其主要的区别是，回溯法在求解过程中不保留完整的树结构，而深度优先搜索则记下完整的搜索树。
4. 为了减少存储空间，在深度优先搜索中，用标志的方法记录访问过的状态，这种处理方法使得深度优先搜索法与回溯法没什么区别了。

回溯

解决一个回溯问题，实际上就是一个决策树的遍历过程.
回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做⼀些操作，算法框架如下：

框架

多叉树的遍历框架

图的遍历操作

回溯遍历框架

写 backtrack 函数时，需要维护⾛过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时， 将「路径」记⼊结果集。

子集相关问题

无论是排列、组合还是子集问题，简单说无非就是让你从序列nums中以给定规则取若干元素，主要有以下几种变体：

形式一、元素无重不可复选，即nums中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式。（78，77，46）

以组合为例，如果输入nums = [2,3,6,7]，和为 7 的组合应该只有[7]。

形式二、元素可重不可复选，即nums中的元素可以存在重复，每个元素最多只能被使用一次。（90，40，47）

以组合为例，如果输入nums = [2,5,2,1,2]，和为 7 的组合应该有两种[2,2,2,1]和[5,2]。

形式三、元素无重可复选，即nums中的元素都是唯一的，每个元素可以被使用若干次。（39）

以组合为例，如果输入nums = [2,3,6,7]，和为 7 的组合应该有两种[2,2,3]和[7]。

当然，也可以说有第四种形式，即元素可重可复选。但既然元素可复选，那又何必存在重复元素呢？元素去重之后就等同于形式三，所以这种情况不用考虑。

上面用组合问题举的例子，但排列、组合、子集问题都可以有这三种基本形式，所以共有 9 种变化。

除此之外，题目也可以再添加各种限制条件，比如让你求和为target且元素个数为k的组合，那这么一来又可以衍生出一堆变体，怪不得面试笔试中经常考到排列组合这种基本题型。

但无论形式怎么变化，其本质就是穷举所有解，而这些解呈现树形结构，所以合理使用回溯算法框架，稍改代码框架即可把这些问题一网打尽。
注意：组合问题和子集问题其实是等价的

78. 子集（中等）

使用start参数控制树枝的生长避免产生重复的子集，用path记录根节点到每个节点的路径的值，同时在前序位置把每个节点的路径值收集起来，放入res中，完成回溯树的遍历就收集了所有子集：

class Solution {
    // 记录回溯算法的最终结果
    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    LinkedList<Integer> path = new LinkedList<>();

    // 主函数
    public List<List<Integer>> subsets(int[] nums) {
        traverse(nums, 0);
        return res;
    }

    // 回溯算法核心函数，遍历子集问题的回溯树
    private void traverse(int[] nums, int start) {
        // 前序位置，每个节点的值都是一个子集
        res.add(new LinkedList<>(path));
        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 做选择
            path.add(nums[i]);
            // 通过 start 参数控制树枝的遍历，避免产生重复的子集
            traverse(nums, i + 1);
            // 撤销选择
            path.removeLast();
        }
    }
}
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

最后，backtrack函数开头看似没有 base case，会不会进入无限递归？

其实不会的，当start == nums.length时，叶子节点的值会被装入res，但 for 循环不会执行，也就结束了递归。

90. 子集 II（中等）

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 先排序，让相同的元素靠在一起
        Arrays.sort(nums);
        traverse(nums, 0);
        return res;
    }

    private void traverse(int[] nums, int start) {
        // 前序位置，每个节点的值都是一个子集
        res.add(new LinkedList<>(path));
        for (int i = start; i < nums.length; i++) {
            // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            traverse(nums, i + 1);
            path.removeLast();
        }
    }
}
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

77. 组合（中等）

这就是典型的回溯算法，k 限制了树的高度，n 限制了树的宽度，直接套我们以前讲过的回溯算法模板框架就行了。
还是以nums = [1,2,3]为例，刚才让你求所有子集，就是把所有节点的值都收集起来；现在你只需要把第 2 层（根节点视为第 0 层）的节点收集起来，就是大小为 2 的所有组合：

class Solution {
    // 记录回溯算法的最终结果
    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    LinkedList<Integer> path = new LinkedList<>();

    // 主函数
    public List<List<Integer>> combine(int n, int k) {
        int[] nums = new int[n];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = i + 1;
        }
        traverse(nums, 0, k);
        return res;
    }

    // 回溯算法核心函数，遍历子集问题的回溯树
    private void traverse(int[] nums, int start, int k) {
        // base case
        if (path.size() == k) {
            // 遍历到了第 k 层，收集当前节点的值
            res.add(new LinkedList<>(path));
            return;
        }
        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 做选择
            path.add(nums[i]);
            // 通过 start 参数控制树枝的遍历，避免产生重复的子集
            traverse(nums, i + 1, k);
            // 撤销选择
            path.removeLast();
        }
    }
}
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

排列问题每次通过 contains 方法来排除在 track 中已经选择过的数字；而组合问题通过传入一个 start 参数，来排除 start 索引之前的数字。

39. 组合总和（中等）

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯的路径
    LinkedList<Integer> path = new LinkedList<>();
    // 记录 track 中的路径和
    int sum;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        traverse(candidates, 0, target);
        return res;
    }

    // 回溯算法主函数
    private void traverse(int[] nums, int start, int target) {
        // base case，找到目标和，记录结果
        if (sum == target) {
            res.add(new LinkedList<>(path));
            return;
        }
        // base case，超过目标和，停止向下遍历
        if (sum > target) {
            return;
        }
        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 选择 nums[i]
            path.add(nums[i]);
            sum += nums[i];
            // 递归遍历下一层回溯树
            // 同一元素可重复使用，注意参数
            traverse(nums, i, target);
            // 撤销选择 nums[i]
            sum -= nums[i];
            path.removeLast();
        }
    }
}
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

40. 组合总和 II（中等）

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯的路径
    LinkedList<Integer> path = new LinkedList<>();
    // 记录 path 中的元素之和
    int sum;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 先排序，让相同的元素靠在一起
        Arrays.sort(candidates);
        traverse(candidates, 0, target);
        return res;
    }

    // 回溯算法主函数
    private void traverse(int[] nums, int start, int target) {
        // base case，达到目标和，找到符合条件的组合
        if (sum == target) {
            res.add(new LinkedList<>(path));
            return;
        }
        // base case，超过目标和，直接结束
        if (sum > target) {
            return;
        }
        // 回溯算法标准框架
        for (int i = start; i < nums.length; i++) {
            // 剪枝逻辑，值相同的树枝，只遍历第一条
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            // 做选择
            path.add(nums[i]);
            sum += nums[i];
            // 递归遍历下一层回溯树
            traverse(nums, i + 1, target);
            // 撤销选择
            sum -= nums[i];
            path.removeLast();
        }
    }
}
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
41
42

216. 组合总和 III（中等）

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        LinkedList<Integer> path = new LinkedList<>();
        backtrace(path, n, k, 1, 0);
        return res;
    }

    private void backtrace(LinkedList<Integer> path, int n, int k, int start, int sum) {
        if (sum == n && path.size() == k) {
            res.add(new LinkedList<>(path));
            return;
        }
        if (sum > n || path.size() >= k) return;
        for (int i = start; i <= 9; i++) {
            path.add(i);
            backtrace(path, n, k, i + 1, sum + i);
            path.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

46. 排列（中等）

used数组标记已经在路径上的元素避免重复选择，然后收集所有叶子节点上的值

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    LinkedList<Integer> path = new LinkedList<>();
    // path 中的元素会被标记为 true
    boolean[] visited;

    /* 主函数，输入一组不重复的数字，返回它们的全排列 */
    public List<List<Integer>> permute(int[] nums) {
        visited = new boolean[nums.length];
        traverse(nums);
        return res;
    }

    // 回溯算法核心函数
    private void traverse(int[] nums) {
        // base case，到达叶子节点
        if (path.size() == nums.length) {
            // 收集叶子节点上的值
            res.add(new LinkedList<>(path));
            return;
        }
        // 回溯算法标准框架
        for (int i = 0; i < nums.length; i++) {
            // 已经存在 track 中的元素，不能重复选择
            if (!visited[i]) {
                // 做选择
                path.add(nums[i]);
                visited[i] = true;
                // 进入下一层回溯树
                traverse(nums);
                // 取消选择
                visited[i] = false;
                path.removeLast();
            }
        }
    }
}
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

47. 全排列 II（中等）

标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复。
画一下决策树就明白了。
当出现重复元素时，比如输入nums = [1,2,2’,2’’]，2’只有在2已经被使用的情况下才会被选择，2’'只有在2’已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定。

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] visited;

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 先排序，让相同的元素靠在一起
        Arrays.sort(nums);
        visited = new boolean[nums.length];
        traverse(nums);
        return res;
    }

    private void traverse(int[] nums) {
        if (path.size() == nums.length) {
            res.add(new LinkedList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            // 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            visited[i] = true;
            traverse(nums);
            visited[i] = false;
            path.removeLast();
        }
    }
}
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

力扣上没有排列（元素无重可复选）类似的题目，不妨自己想一个
比如输入nums = [1,2,3]，那么这种条件下的全排列共有 3^3 = 27 种：
[
[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]
标准的全排列算法利用used数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有used数组的剪枝逻辑就行了。

List<List<Integer>> res = new LinkedList<>();
    // 记录回溯的路径
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> permuteRepeat(int[] nums) {
        traverse(nums);
        return res;
    }

    // 回溯算法主函数
    private void traverse(int[] nums) {
        // base case，到达叶子节点
        if (path.size() == nums.length) {
            // 收集叶子节点上的值
            res.add(new LinkedList<>(path));
            return;
        }
        // 回溯算法标准框架
        for (int i = 0; i < nums.length; i++) {
            // 做选择
            path.add(nums[i]);
            // 进入下一层回溯树
            traverse(nums);
            // 取消选择
            path.removeLast();
        }
    }
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

只要从树的角度思考，这些问题看似复杂多变，实则改改 base case 就能解决

17. 电话号码的字母组合(中等)

class Solution {
    String[] str = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> res = new LinkedList<>();

    public List<String> letterCombinations(String digits) {
        if (digits.length() == 0) return new LinkedList<>();
        StringBuffer path = new StringBuffer();
        backtrace(digits, path, 0);
        return res;
    }

    private void backtrace(String digits, StringBuffer path, int index) {
        if (path.length() == digits.length()) {
            res.add(path.toString());
            return;
        }
        for (int i = index; i < digits.length(); i++) {//子集
            int k = digits.charAt(i) - '0';
            for (int j = 0; j < str[k].length(); j++) {//排列
                path.append(str[k].charAt(j));
                backtrace(digits, path, i + 1);
                path.deleteCharAt(path.length() - 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

22. 括号生成（中等）

class Solution {
    // 记录所有合法的括号组合
    List<String> res = new LinkedList<>();
    // 回溯过程中的路径
    StringBuffer path = new StringBuffer();

    public List<String> generateParenthesis(int n) {
        // 可用的左括号和右括号数量初始化为 n
        traverse(n, n);
        return res;
    }

    // 可用的左括号数量为 left 个，可用的右括号数量为 rgiht 个
    private void traverse(int left, int right) {
        // 若左括号剩下的多，说明不合法
        if (left > right) {
            return;
        }
        // 数量小于 0 肯定是不合法的
        if (left < 0 || right < 0) {
            return;
        }
        // 当所有括号都恰好用完时，得到一个合法的括号组合
        if (left == 0 && right == 0) {
            res.add(path.toString());
            return;
        }
        // 尝试放一个左括号
        path.append('(');// 选择
        traverse(left - 1, right);
        path.deleteCharAt(path.length() - 1);// 撤消选择
        // 尝试放一个右括号
        path.append(')');// 选择
        traverse(left, right - 1);
        path.deleteCharAt(path.length() - 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
31
32
33
34
35
36
37

对于递归相关的算法，时间复杂度这样计算[递归次数]x[递归函数本身的时间复杂度]
时间复杂度=卡特兰数

698. 划分为k个相等的子集(中等)

class Solution {
    boolean[] visited;

    public boolean canPartitionKSubsets(int[] nums, int k) {
        visited = new boolean[nums.length];
        // 排除⼀些基本情况
        if (k > nums.length) return false;
        int sum = 0;
        for (int v : nums) sum += v;
        if (sum % k != 0) return false;
        int target = sum / k;
        // k 号桶初始什么都没装，从 nums[0] 开始做选择
        return backtrack(k, 0, nums, 0, target);
    }

    boolean backtrack(int bucket, int sum, int[] nums, int start, int target) {
        // base case
        if (bucket == 0) {
            // 所有桶都被装满了，⽽且 nums ⼀定全部⽤完了
            // 因为 target == sum / bucket
            return true;
        }
        if (sum == target) {
            // 装满了当前桶，递归穷举下⼀个桶的选择
            // 让下⼀个桶从 nums[0] 开始选数字
            return backtrack(bucket - 1, 0, nums, 0, target);
        }
        if (sum > target) {
            // 当前桶装不下 nums[i]
            return false;
        }
        // 从 start 开始向后探查有效的 nums[i] 装⼊当前桶
        for (int i = start; i < nums.length; i++) {
            // 剪枝
            if (visited[i]) {
                // nums[i] 已经被装⼊别的桶中
                continue;
            }
            // 做选择，将 nums[i] 装⼊当前桶中
            visited[i] = true;
            sum += nums[i];
            // 递归穷举下⼀个数字是否装⼊当前桶
            if (backtrack(bucket, sum, nums, i + 1, target)) {
                return true;
            }
            // 撤销选择
            visited[i] = false;
            sum -= nums[i];
        }
        // 穷举了所有数字，都⽆法装满当前桶
        return false;
    }
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53

51. N 皇后(困难)

函数backtrack依然像个在决策树上游走的指针，每个节点就表示在board[row][col]上放置皇后，通过isValid函数可以将不符合条件的情况剪枝：

class Solution {
   List<List<String>> res = new LinkedList<>();

    /* 输入棋盘边长 n，返回所有合法的放置 */
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        // '.' 表示空，'Q' 表示皇后，初始化空棋盘。
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        traverse(board, 0);
        return res;
    }

    // 路径：board 中小于 row 的那些行都已经成功放置了皇后
    // 选择列表：第 row 行的所有列都是放置皇后的选择
    // 结束条件：row 超过 board 的最后一行
    private void traverse(char[][] board, int row) {
        // 触发结束条件
        if (row == board.length) {
            List<String> temp = new LinkedList<>();
            for (char[] chars : board) {
                temp.add(new String(chars));
            }
            res.add(temp);
            return;
        }
        for (int i = 0; i < board.length; i++) {
            // 排除不合法选择
            if (isValid(board, row, i)) {
                // 做选择
                board[row][i] = 'Q';
                // 进入下一行决策
                traverse(board, row + 1);
                // 撤销选择
                board[row][i] = '.';
            }
        }
    }
    /* 是否可以在 board[row][col] 放置皇后？ */
    private boolean isValid(char[][] board, int row, int col) {
        for (int i = 0; i < board.length; i++) {
            // 检查列是否有皇后互相冲突
            if (board[i][col] == 'Q') return false;
            // 检查行是否有皇后互相冲突
            if (board[row][i] == 'Q') return false;
        }
        // 检查左上方是否有皇后互相冲突
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') return false;
        }
        // 检查右上方是否有皇后互相冲突
        for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') return false;
        }
        return true;
    }
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

37. 解数独（困难）

public void solveSudoku(char[][] board) {
        traverse(board, 0, 0);
    }

    private boolean traverse(char[][] board, int row, int col) {
        if (row == 9) {
            // 找到一个可行解，触发 base case
            return true;
        }
        // 穷举到最后一列的话就换到下一行重新开始。
        if (col == 9) {
            return traverse(board, row + 1, 0);
        }
        if (board[row][col] != '.') {
            // 如果有预设数字，不用我们穷举
            return traverse(board, row, col + 1);
        }
        for (char ch = '1'; ch <= '9'; ch++) {
            // 如果遇到不合法的数字，就跳过
            if (isValid(board, row, col, ch)) {
                board[row][col] = ch;
                // 如果找到一个可行解，立即结束
                if (traverse(board, row, col + 1)) {
                    return true;
                }
                ;
                board[row][col] = '.';
            }
        }
        // 穷举完 1~9，依然没有找到可行解，此路不通
        return false;
    }

    // 判断 board[r][c] 是否可以填入 n
    private boolean isValid(char[][] board, int row, int col, char ch) {
        for (int i = 0; i < board.length; i++) {
            // 判断行是否存在重复
            if (board[row][i] == ch) return false;
            // 判断列是否存在重复
            if (board[i][col] == ch) return false;
            // 判断 3 x 3 方框是否存在重复
            if (board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == ch) return false;
        }
        return true;
    }
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
41
42
43
44
45

总结

子集问题可以利用数学归纳思想，假设已知一个规模较小的问题的结果，思考如何推导出原问题的结果。也可以用回溯算法，要用 start 参数排除已选择的数字。

组合问题利用的是回溯思想，结果可以表示成树结构，我们只要套用回溯算法模板即可，关键点在于要用一个 start 排除已经选择过的数字。

排列问题是回溯思想，也可以表示成树结构套用算法模板，不同之处在于使用 contains 方法排除已经选择的数字.

写backtrack函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

其实想想看，回溯算法和动态规划是不是有点像呢？我们在动态规划系列文章中多次强调，动态规划的三个需要明确的点就是「状态」「选择」和「base case」，是不是就对应着走过的「路径」，当前的「选择列表」和「结束条件」？

某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。

DFS

框架

// ⼆叉树遍历框架
    public void traverse(TreeNode root) {
        traverse(root.left);
        traverse(root.right);
    }
1
2
3
4
5

// ⼆维矩阵遍历框架
    public void dfs(int[][] grid, int i, int j, Boolean[][] visited) {
        int m = grid.length, n = grid[0].length;
        if (i < 0 || j < 0 || i >= m || j >= n) {
            // 超出索引边界
            return;
        }
        if (visited[i][j] == true) {
            // 已遍历过 (i, j)
            return;
        }
        // 进⼊节点 (i, j)
        visited[i][j] = true;
        dfs(grid, i - 1, j, visited);// 上
        dfs(grid, i + 1, j, visited); // 下
        dfs(grid, i, j - 1, visited); // 左
        dfs(grid, i, j + 1, visited); // 右
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

200. 岛屿数量（中等）(FloodFill算法)

class Solution {
    // 主函数，计算岛屿数量
    public int numIslands(char[][] grid) {
        int res = 0;
        // 遍历 grid
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    res++;  // 每发现⼀个岛屿，岛屿数量加⼀
                }
                dfs(grid, i, j);    // 然后使⽤ DFS 将岛屿淹了
            }
        }
        return res;
    }

    // 从 (i, j) 开始，将与之相邻的陆地都变成海⽔
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return;  // 超出索引边界
        if (grid[i][j] == '0') return;  //已经是海⽔了
        grid[i][j] = '0';//将 (i, j) 变成海⽔
        //淹没上下左右的陆地
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 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

1254. 统计封闭岛屿的数目（中等）

class Solution {
    // 主函数，计算岛屿数量
    public int closedIsland(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int res = 0;
        // 遍历 grid
        for (int j = 0; j < m; j++) {
            dfs(grid, 0, j);
            dfs(grid, n - 1, j);
        }
        for (int i = 0; i < n; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, m - 1);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    res++;  // 每发现⼀个岛屿，岛屿数量加⼀
                }
                dfs(grid, i, j);    // 然后使⽤ DFS 将岛屿淹了
            }
        }
        return res;
    }

    // 从 (i, j) 开始，将与之相邻的陆地都变成海⽔
    private void dfs(int[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return;  // 超出索引边界
        if (grid[i][j] == 1) return;  //已经是海⽔了
        grid[i][j] = 1;//将 (i, j) 变成海⽔
        //淹没上下左右的陆地
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 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
31
32
33
34
35
36
37

1020. 飞地的数量(中等)

class Solution {
    // 主函数，计算岛屿数量
    public int numEnclaves(int[][] grid) {
        int n = grid.length, m = grid[0].length;
        int res = 0;
        // 遍历 grid
        for (int j = 0; j < m; j++) {
            dfs(grid, 0, j);
            dfs(grid, n - 1, j);
        }
        for (int i = 0; i < n; i++) {
            dfs(grid, i, 0);
            dfs(grid, i, m - 1);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    res++;  // 每发现⼀个岛屿，岛屿数量加⼀
                }
               
            }
        }
        return res;
    }

    // 从 (i, j) 开始，将与之相邻的陆地都变成海⽔
    private void dfs(int[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return;  // 超出索引边界
        if (grid[i][j] == 0) return;  //已经是海⽔了
        grid[i][j] = 0;//将 (i, j) 变成海⽔
        //淹没上下左右的陆地
        dfs(grid, i - 1, j);
        dfs(grid, i + 1, j);
        dfs(grid, i, j - 1);
        dfs(grid, i, j + 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
31
32
33
34
35
36
37

1905. 统计子岛屿(中等)

public int countSubIslands(int[][] grid1, int[][] grid2) {
        int n = grid1.length, m = grid1[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid2[i][j] == 1 && grid1[i][j] == 0) {
                    dfs(grid2, i, j);
                }
            }
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid2[i][j] == 1) {
                    ret++;
                    //这个岛屿肯定不是⼦岛，淹掉
                    dfs(grid2, i, j);
                }
            }
        }
        return ret;
    }
    //从 (i, j) 开始，将与之相邻的陆地都变成海⽔
    private void dfs(int[][] grid2, int i, int j) {
        int n = grid2.length, m = grid2[0].length;
        if (i < 0 || j < 0 || i >= n || j >= m) return;
        if (grid2[i][j] == 0) return;
        grid2[i][j] = 0;
        dfs(grid2, i - 1, j);
        dfs(grid2, i + 1, j);
        dfs(grid2, i, j - 1);
        dfs(grid2, i, j + 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
31
32

79. 单词搜索（中等）

阿里面试题，在二维数组中搜索“alibaba”，当时不会做。。
用模板写出来，虽然增加了很多无关的操作，但是想通过这道题举一反三。
后期可能会优化一下。

时空复杂度：3^l * MN、MN

class Solution {
    List<LinkedList<Character>> res = new LinkedList<>();//存放结果

    public boolean exist(char[][] board, String word) {
        boolean[][] visited = new boolean[board.length][board[0].length];//记录是否被访问过
        LinkedList<Character> path = new LinkedList<>();//记录当前路径
        //从不同起点出发
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs(board, i, j, path, visited, word, 0);//dfs返回以i，j起点得到的满足题意的字符串
            }
        }
        //res中存放多个满足题意的结果
        if (res.size() == 0) return false;
        return true;
    }

    private void dfs(char[][] board, int i, int j, LinkedList<Character> path, boolean[][] visited, String word, int k) {
        int n = board.length, m = board[0].length; //row和col
        if (i < 0 || j < 0 || i >= n || j >= m) return; // 超出索引边界
        if (visited[i][j] == true) return; //访问过返回
        visited[i][j] = true; // 已遍历过 (i, j)
        path.add(board[i][j]); //将当前节点放到访问路径path中
        if (path.get(k) != word.charAt(k)) {//节点不符合，提前剪枝
            path.removeLast();  //撤销加入节点操作并将该节点设为false
            visited[i][j] = false;
            return;
        }
        if (k == word.length() - 1) {   //满足题意返回，返回前撤销
            res.add(new LinkedList<>(path));
            path.removeLast();
            visited[i][j] = false;
            return;
        }
        dfs(board, i - 1, j, path, visited, word, k + 1);//上
        dfs(board, i + 1, j, path, visited, word, k + 1);//下
        dfs(board, i, j - 1, path, visited, word, k + 1);//左
        dfs(board, i, j + 1, path, visited, word, k + 1);//右
        visited[i][j] = false;
        path.removeLast();                                  //撤销
    }
}
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
41
42

212. 单词搜索 II （困难）

class Solution {
    List<String> res = new LinkedList<>();
    boolean flag;

    public List<String> findWords(char[][] board, String[] words) {
        int n = board.length, m = board[0].length;
        StringBuffer path = new StringBuffer();
        boolean[][] vistied = new boolean[n][m];
        for (int k = 0; k < words.length; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    flag = false;
                    dfs(board, i, j, words[k], vistied, 1);
                    
                    if (flag){
                        res.add(words[k]);
                        break;
                    } 
                }
                if (flag) break;
            }
        }
        HashSet<String> hashSet = new HashSet<>();
        for (String re : res) {
            hashSet.add(re);
        }
        res.removeAll(res);
        for (String s : hashSet) {
            res.add(s);
        }
        return res;
    }

    private void dfs(char[][] board, int i, int j, String word, boolean[][] vistied, int k) {
        int n = board.length, m = board[0].length; //1、base case
        if (i < 0 || j < 0 || i >= n || j >= m) return;//1.1、越界返回
        if (vistied[i][j]) return;                     //1.2、访问过返回
        if (flag) return;
        vistied[i][j] = true;                            //访问过当前节点
        //3、值不一样，剪枝，因为操作2，所以要进行撤销
        if (board[i][j] != word.charAt(k - 1)) {
            vistied[i][j] = false;
            return;
        }
        if (k == word.length()) { //4、符合要求的节点荷属也满足要求，加入结果集中返回
            vistied[i][j] = false;
            flag = true;
            return;
        }
        dfs(board, i - 1, j, word, vistied, k + 1);
        dfs(board, i + 1, j, word, vistied, k + 1);
        dfs(board, i, j - 1, word, vistied, k + 1);
        dfs(board, i, j + 1, word, vistied, k + 1);
        vistied[i][j] = false;
    }
}
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

BFS

框架

// 计算从起点 start 到终点 target 的最近距离 
    int BFS(Node start, Node target) {
        // 核⼼数据结构 
        Queue<Node> q;
        Set<Node> visited; // 避免⾛回头路
        q.offer(start); // 将起点加⼊队列 
        visited.add(start);
        int step = 0; // 记录扩散的步数
        while (q not empty){
            int sz = q.size();
            /* 将当前队列中的所有节点向四周扩散 */
            for (int i = 0; i < sz; i++) {
                Node poll = q.poll(); /* 划重点：这⾥判断是否到达终点 */
                if (poll is target)return step;
                /* 将 poll 的相邻节点加⼊队列 */
                for (Node x : poll.adj()) {
                    if (x not in visited){
                        q.offer(x);
                        visited.add(x);
                    }
                }
            }
            /* 划重点：更新步数在这⾥ */
            step++;
        }
    }
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

111. 二叉树的最小深度（中等）

class Solution {
    public int minDepth(TreeNode root) {
        return traverse(root);
    }

    private int traverse(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;// root 本身就是⼀层，depth 初始化为 1
        while (!queue.isEmpty()) {
            int size = queue.size();
            /* 将当前队列中的所有节点向四周扩散 */
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                /* 判断是否到达终点 */
                if (poll.left == null && poll.right == null) {
                    return depth;
                }
                /* 将 cur 的相邻节点加⼊队列 */
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
            /* 这⾥增加步数 */
            depth++;
        }
        return depth;
    }
}
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

752. 打开转盘锁（中等）

1

总结

其中，DFS 算法和回溯算法可以说是师出同⻔，⼤同⼩异，图论算法基础 探讨过这个问题，区别仅仅在于根 节点是否被遍历到⽽已。

另外，你应该注意到了，这个 onPath 数组的操作很像 回溯算法核⼼套路 中做「做选择」和「撤销选择」， 区别在于位置：回溯算法的「做选择」和「撤销选择」在 for 循环⾥⾯，⽽对 onPath 数组的操作在 for 循环 外⾯。
在 for 循环⾥⾯和外⾯唯⼀的区别就是对根节点的处理。
⽐如下⾯两种多叉树的遍历：

void traverse(TreeNode root) {
        if (root == null) return;
        System.out.println("enter: " + root.val);
        for (TreeNode child : root.children) {
            traverse(child);
        }
        System.out.println("leave: " + root.val);
    }

    void traverse2(TreeNode root) {
        if (root == null) return;
        for (TreeNode child : root.children) {
            System.out.println("enter: " + child.val);
            traverse(child);
            System.out.println("leave: " + child.val);
            List<List<Integer>> res = new LinkedList<>();

        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

前者会正确打印所有节点的进⼊和离开信息，⽽后者唯独会少打印整棵树根节点的进⼊和离开信息。 为什么回溯算法框架会⽤后者？因为回溯算法关注的不是节点，⽽是树枝。
显然，对于这⾥「图」的遍历，我们应该把 onPath 的操作放到 for 循环外⾯，否则会漏掉记录起始点的遍
历。
说了这么多 onPath 数组，再说下 visited 数组，其⽬的很明显了，由于图可能含有环，visited 数组就 是防⽌递归重复遍历同⼀个节点进⼊死循环的。
当然，如果题⽬告诉你图中不含环，可以把 visited 数组都省掉，基本就是多叉树的遍历。

BFS 算法常⻅于求最值的场景，因为 BFS 的算法逻辑保证了算法第⼀次到达⽬标时的代价是最⼩的。