力扣刷题：DFS篇

墨蓝 2022-10-16 09:40 199阅读 0赞

### 目录 ###

*  112. 路径总和
 *   *  题目介绍
     *  题目实现
 *  113. 路径总和 II
 *   *  题目介绍
     *  题目实现
 *  17. 电话号码的字母组合
 *   *  题目介绍
     *  题目实现
 *  22. 括号生成
 *   *  题目介绍
     *  题目实现
 *  39. 组合总和
 *   *  题目介绍
     *  题目实现
 *  46. 全排列
 *   *  题目介绍
     *  题目实现
 *  47. 全排列 II
 *   *  题目介绍
     *  题目实现
 *  79. 单词搜索
 *   *  题目介绍
     *   *   *  \[剑指 Offer 12. 矩阵中的路径\](https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/)
     *  题目实现
 *  剑指 Offer 13. 机器人的运动范围
 *   *  题目介绍
     *  题目实现

--------------------

# 112. 路径总和 #

## 题目介绍 ##

给你二叉树的根节点 `root` 和一个表示目标和的整数 `targetSum` ，判断该树中是否存在 **根节点到叶子节点** 的路径，这条路径上所有节点值相加等于目标和 `targetSum` 。

**叶子节点** 是指没有子节点的节点。

**示例 1：**

![6a0e57cf45346791eee10cd3e2c056dc.png][]

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
    输出：true

**示例 2：**

![a7982018cfb4033f1d2111f675713e1f.png][]

输入：root = [1,2,3], targetSum = 5
    输出：false

**示例 3：**

输入：root = [1,2], targetSum = 0
    输出：false

**提示：**

*  树中节点的数目在范围 \[0, 5000\] 内
 *  \-1000 <= Node.val <= 1000
 *  \-1000 <= targetSum <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/path-sum  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。

当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

class Solution { 
        public boolean hasPathSum(TreeNode root, int targetSum) { 
            List<List<Integer>> list = new ArrayList<>();
            dfs(root, targetSum, new ArrayList<>(), list);
            return !list.isEmpty();
        }
    
        /** * 深度优先搜索匹配路径，从数根开始，向树叶方向搜索 * * @param node 当前节点 * @param remain 剩余数值 * @param nums 用于保存搜索过的节点值 * @param list 用于保存已匹配上的路径 */
        private void dfs(TreeNode node, int remain, List<Integer> nums, List<List<Integer>> list) { 
            if (node == null) return;
            nums.add(node.val);
            // 如果搜索到叶子节点，并且 remain 等于叶子节点的值，说明此路径匹配
            if (node.left == null && node.right == null && node.val == remain) { 
                list.add(new ArrayList<>(nums));
            }
            // 深度优先搜索 node 节点的左子树
            dfs(node.left, remain - node.val, nums, list);
            // 深度优先搜索 node 节点的右子树
            dfs(node.right, remain - node.val, nums, list);
            // 回溯的时候需要删除最后一个数值
            nums.remove(nums.size() - 1);
        }
    }

# 113. 路径总和 II #

## 题目介绍 ##

给你二叉树的根节点 `root` 和一个整数目标和 `targetSum` ，找出所有 **从根节点到叶子节点** 路径总和等于给定目标和的路径。

**叶子节点** 是指没有子节点的节点。

**示例 1：**

![48791728f3f42c9a9adda30686be7a4e.png][]

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
    输出：[[5,4,11,2],[5,8,4,5]]

**示例 2：**

![7ed122a1877055ce152f7d8bcff01400.png][]

输入：root = [1,2,3], targetSum = 5
    输出：[]

**示例 3：**

输入：root = [1,2], targetSum = 0
    输出：[]

**提示：**

*  树中节点总数在范围 \[0, 5000\] 内
 *  \-1000 <= Node.val <= 1000
 *  \-1000 <= targetSum <= 1000

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/path-sum-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。

当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

class Solution { 
        public List<List<Integer>> pathSum(TreeNode root, int targetSum) { 
            List<List<Integer>> list = new ArrayList<>();
            dfs(root, targetSum, new ArrayList<>(), list);
            return list;
        }
    
        /** * 深度优先搜索匹配路径，从数根开始，向树叶方向搜索 * * @param node 当前节点 * @param remain 剩余数值 * @param nums 用于保存搜索过的节点值 * @param list 用于保存已匹配上的路径 */
        private void dfs(TreeNode node, int remain, List<Integer> nums, List<List<Integer>> list) { 
            if (node == null) return;
            nums.add(node.val);
            // 如果搜索到叶子节点，并且 remain 等于叶子节点的值，说明此路径匹配
            if (node.left == null && node.right == null && node.val == remain) { 
                list.add(new ArrayList<>(nums));
            }
            // 深度优先搜索 node 节点的左子树
            dfs(node.left, remain - node.val, nums, list);
            // 深度优先搜索 node 节点的右子树
            dfs(node.right, remain - node.val, nums, list);
            // 回溯的时候需要删除最后一个数值
            nums.remove(nums.size() - 1);
        }
    }

# 17. 电话号码的字母组合 #

## 题目介绍 ##

给定一个仅包含数字 `2-9` 的字符串，返回所有它能表示的字母组合。答案可以按 `任意顺序` 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 `1` 不对应任何字母。

![b6e536fea39fe370282a734c844e7816.png][]

**示例 1：**

输入：digits = "23"
    输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

**示例 2：**

输入：digits = ""
    输出：[]

**示例 3：**

输入：digits = "2"
    输出：["a","b","c"]

**提示：**

*  0 <= digits.length <= 4
 *  digits\[i\] 是范围 \[‘2’, ‘9’\] 的一个数字。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

定义一个 `string` 字符数组，用来存储每次遍历完以后，当前遍历过的字符串。整个过程我们使用dfs深度优先，搜索完一个结果后就会回溯到上一层，然后继续向下层查找，直到下一层越界为止。这里给出两个示例图：

输入：digits = “23”

![c397b7a4efc3b713d3d4b31333a003aa.png][]

输入：digits = “256”

![ea2491e0357b9b3e25073b16babb5301.png][]

class Solution { 
        public List<String> letterCombinations(String digits) { 
            if (digits == null) return null;
            List<String> list = new ArrayList<>();
            char[] chars = digits.toCharArray();
            if (chars.length == 0) return list;
            char[] string = new char[chars.length];
            dfs(0, chars, string, list);
            return list;
        }
    
        private char[][] lettersArray = { 
            { 'a', 'b', 'c'}, { 'd', 'e', 'f'}, { 'g', 'h', 'i'},
            { 'j', 'k', 'l'}, { 'm', 'n', 'o'}, { 'p', 'q', 'r', 's'},
            { 't', 'u', 'v'}, { 'w', 'x', 'y', 'z'}
        };
    
        private void dfs(int index, char[] chars, char[] string, List<String> list) { 
            // 不能再往下搜索
            if (index == chars.length) { 
                list.add(new String(string));
                return;
            }
            // 枚举这一层元素
            char[] letters = lettersArray[chars[index] - '2'];
            for (char letter : letters) { 
                string[index] = letter;
                dfs(index + 1, chars, string, list);
            }
        }
    }

# 22. 括号生成 #

## 题目介绍 ##

数字 `n` 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 **有效的** 括号组合。

**示例 1：**

输入：n = 3
    输出：["((()))","(()())","(())()","()(())","()()()"]

**示例 2：**

输入：n = 1
    输出：["()"]

**提示：**

*  1 <= n <= 8

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/generate-parentheses  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

*  如果 cur 长度达到 n 的两倍，说明完成了一次括号匹配。
 *  如果左括号数量小于 n 的数量，我们可以放一个左括号。
 *  如果右括号数量小于左括号的数量，我们可以放一个右括号。

class Solution { 
        public List<String> generateParenthesis(int n) { 
            List<String> list = new ArrayList<String>();
            dfs(list, new StringBuilder(), 0, 0, n);
            return list;
        }
    
        public void dfs(List<String> list, StringBuilder cur, int open, int close, int n) { 
            // 如果 cur 长度达到 n 的两倍，说明完成了一次括号匹配。
            if (cur.length() == n * 2) { 
                list.add(cur.toString());
                return;
            }
            // 如果左括号数量小于 n 的数量，我们可以放一个左括号。
            if (open < n) { 
                cur.append('(');
                dfs(list, cur, open + 1, close, n);
                cur.deleteCharAt(cur.length() - 1);
            }
            // 如果右括号数量小于左括号的数量，我们可以放一个右括号。
            if (close < open) { 
                cur.append(')');
                dfs(list, cur, open, close + 1, n);
                cur.deleteCharAt(cur.length() - 1);
            }
        }
    }

另外一种做法就是：动态规划

class Solution { 
        public static List<String> generateParenthesis(int n) { 
            ArrayList<HashSet<String>> dp = new ArrayList<>();
            //初始
            for (int i = 0; i <= n; i++) { 
                dp.add(new HashSet<>());
            }
            dp.get(1).add("()");
            //核心
            for (int i = 2; i <= n; i++) { 
                for (String s : dp.get(i - 1)) { 
                    dp.get(i).add("(" + s + ")");
                    dp.get(i).add("()" + s);
                    dp.get(i).add(s + "()");
                }
                for (int j = 2; j <= i / 2; j++) { 
                    for (String str1 : dp.get(j)) { 
                        for (String str2 : dp.get(i - j)) { 
                            dp.get(i).add(str1 + str2);
                            dp.get(i).add(str2 + str1);
                        }
                    }
                }
            }
            return new ArrayList<>(dp.get(n));
        }
    }

# 39. 组合总和 #

## 题目介绍 ##

给定一个无重复元素的数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。

`candidates` 中的数字可以无限制重复被选取。

**说明：**

*  所有数字（包括 `target`）都是正整数。
 *  解集不能包含重复的组合。

**示例 1：**

输入：candidates = [2,3,6,7], target = 7,
    所求解集为：
    [
      [7],
      [2,2,3]
    ]

**示例 2：**

输入：candidates = [2,3,5], target = 8,
    所求解集为：
    [
      [2,2,2,2],
      [2,3,3],
      [3,5]
    ]

**提示：**

*  1 <= candidates.length <= 30
 *  1 <= candidates\[i\] <= 200
 *  candidate 中的每个元素都是独一无二的。
 *  1 <= target <= 500

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/combination-sum  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

以输入：`candidates = [2, 3, 6, 7]`, `target = 7` 为例：

![e6a7aedf9ce0d3e6f19db828e223f937.png][]

**说明**：

*  以 `target = 7` 为 **根结点** ，创建一个分支的时 **做减法** ；
 *  每一个箭头表示：从父亲结点的数值减去边上的数值，得到孩子结点的数值。边的值就是题目中给出的 `candidate` 数组的每个元素的值；
 *  减到 0 或者负数的时候停止，即：结点 0 和负数结点成为叶子结点；
 *  所有从根结点到结点 00 的路径（只能从上往下，没有回路）就是题目要找的一个结果。

这棵树有 4 个叶子结点的值 0，对应的路径列表是 `[[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]]`，而示例中给出的输出只有 `[[7], [2, 2, 3]]`。即：题目中要求每一个符合要求的解是 **不计算顺序** 的。

class Solution { 
        public List<List<Integer>> combinationSum(int[] candidates, int target) { 
            List<List<Integer>> list = new ArrayList<>();
            dfs(candidates, 0, target, new ArrayList<>(), list);
            return list;
        }
    
        private void dfs(int[] candidates,int begin,int remain,List<Integer> nums,List<List<Integer>> list){ 
            // 如果剩余数值小于0，则表示行不通，直接返回
            if (remain < 0) { 
                return;
            }
            // 如果剩余数值等于0，则表示行得通，保存结果
            if (remain == 0) { 
                list.add(new ArrayList<>(nums));
                return;
            }
            // 如果剩余数值大于0，则循环遍历进行深度搜索
            for (int i = begin; i < candidates.length; i++) { 
                nums.add(candidates[i]);
                dfs(candidates, i, remain - candidates[i], nums, list);
                nums.remove(nums.size() - 1);
            }
        }
    }

# 46. 全排列 #

## 题目介绍 ##

给定一个不含重复数字的数组 `nums` ，返回其 所有可能的全排列 。你可以 `按任意顺序` 返回答案。

**示例 1：**

输入：nums = [1,2,3]
    输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

**示例 2：**

输入：nums = [0,1]
    输出：[[0,1],[1,0]]

**示例 3：**

输入：nums = [1]
    输出：[[1]]

**提示：**

*  1 <= nums.length <= 6
 *  \-10 <= nums\[i\] <= 10
 *  nums 中的所有整数 互不相同

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/permutations  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![3736a76bbe2d2cc0a744926d621d914f.png][]

class Solution { 
        public List<List<Integer>> permute(int[] nums) { 
            if (nums == null) return null;
            List<List<Integer>> list = new ArrayList<>();
            if (nums.length == 0) return list;
            dfs(0, nums, list);
            return list;
        }
    
        private void dfs(int index, int[] nums, List<List<Integer>> list) { 
            // 不能再往下搜索
            if (index == nums.length) { 
                List<Integer> ans = new ArrayList<>();
                for (int num : nums) { 
                    ans.add(num);
                }
                list.add(ans);
                return;
            }
            // 枚举这一层元素
            for (int i = index; i < nums.length; i++) { 
                swap(nums, index, i);//交换元素
                dfs(index + 1, nums, list);
                swap(nums, index, i);//还原现场
            }
        }
    
        private void swap(int[] nums, int i, int j) { 
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

# 47. 全排列 II #

## 题目介绍 ##

给定一个可包含重复数字的序列 `nums` ，按任意顺序 返回所有不重复的全排列。

**示例 1：**

输入：nums = [1,1,2]
    输出：
    [[1,1,2],
     [1,2,1],
     [2,1,1]]

**示例 2：**

输入：nums = [1,2,3]
    输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

**提示：**

*  1 <= nums.length <= 8
 *  \-10 <= nums\[i\] <= 10

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/permutations-ii  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

![a2bf050644f14649904af39a602f4727.png][]

此题是「[46. 全排列][46.]」的进阶，序列中包含了重复的数字，要求我们返回不重复的全排列，那么我们依然可以选择使用搜索回溯的方法来做。如果只使用上述解题的递归函数，我们会生成大量重复的排列，因为对于第 index 的位置，如果存在重复的数字 i，我们每次会将重复的数字都重新填上去并继续尝试导致最后答案的重复，因此我们需要处理这个情况。要解决重复问题，我们只要设定一个规则，保证在填第 index 个数的时候重复数字只会被填入一次即可。

class Solution { 
        public List<List<Integer>> permuteUnique(int[] nums) { 
            if (nums == null) return null;
            List<List<Integer>> list = new ArrayList<>();
            if (nums.length == 0) return list;
            dfs(0, nums, list);
            return list;
        }
    
        private void dfs(int index, int[] nums, List<List<Integer>> list) { 
            // 不能再往下搜索
            if (index == nums.length) { 
                List<Integer> ans = new ArrayList<>();
                for (int num : nums) { 
                    ans.add(num);
                }
                list.add(ans);
                return;
            }
            // 枚举这一层元素
            for (int i = index; i < nums.length; i++) { 
                // 要保证一个数字在 index 位置只会出现一次
                if (isRepeat(nums, index, i)) continue;
    
                swap(nums, index, i);//交换元素
                dfs(index + 1, nums, list);
                swap(nums, index, i);//还原现场
            }
        }
    
        private void swap(int[] nums, int i, int j) { 
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    
        private boolean isRepeat(int[] nums, int index, int i) { 
            for (int j = index; j < i; j++) { 
                if (nums[j] == nums[i]) { 
                    return true;
                }
            }
            return false;
        }
    }

# 79. 单词搜索 #

## 题目介绍 ##

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

**示例 1：**

![43c405bbda4b74195e5b95fbbdf62b47.png][]

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
    输出：true

**示例 2：**

![10d535d7f9fa07f978047dd57d69252a.png][]

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
    输出：true

**示例 3：**

![a7e8be41487000d45e538e93eb52aef9.png][]

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
    输出：false

**提示：**

*  m == board.length
 *  n = board\[i\].length
 *  1 <= m, n <= 6
 *  1 <= word.length <= 15
 *  board 和 word 仅由大小写英文字母组成

**进阶：**

*  你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？

**相同题目：**

*  #### [剑指 Offer 12. 矩阵中的路径][Offer 12.] ####

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/word-search  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        public boolean exist(char[][] board, String word) { 
            for (int i = 0; i < board.length; i++) { 
                for (int j = 0; j < board[0].length; j++) { 
                    if (dfs(board, word, i, j, 0)) { 
                        return true;
                    }
                }
            }
            return false;
        }
    
        private boolean dfs(char[][] board, String word, int i, int j, int k) { 
            //临界条件
            if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(k)) { 
                return false;
            }
            //搜索结束
            if (k == word.length() - 1) { 
                return true;
            }
            //搜索完成
            board[i][j] = 0;
            //上下左右
            boolean res = dfs(board, word, i - 1, j, k + 1) ||
                    dfs(board, word, i + 1, j, k + 1) ||
                    dfs(board, word, i, j - 1, k + 1) ||
                    dfs(board, word, i, j + 1, k + 1);
            //还原现场
            board[i][j] = word.charAt(k);
            //返回结果
            return res;
        }
    }

# 剑指 Offer 13. 机器人的运动范围 #

## 题目介绍 ##

地上有一个m行n列的方格，从坐标 \[0,0\] 到坐标 \[m-1,n-1\] 。一个机器人从坐标 \[0, 0\] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 \[35, 37\] ，因为3+5+3+7=18。但它不能进入方格 \[35, 38\]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

**示例 1：**

输入：m = 2, n = 3, k = 1
    输出：3

**示例 2：**

输入：m = 3, n = 1, k = 0
    输出：1

**提示：**

*  1 <= n,m <= 100
 *  0 <= k <= 20

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 题目实现 ##

class Solution { 
        private int count = 0;
        private boolean[][] visited;
    
        public int movingCount(int m, int n, int k) { 
            visited = new boolean[m][n];
            dfs(m, n, 0, 0, k);
            return count;
        }
    
        private void dfs(int m, int n, int i, int j, int k) { 
            //临界条件
            if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || calc(i, j) > k) { 
                return;
            }
            //已经走过
            visited[i][j] = true;
            //更新最值
            count++;
            //上下左右
            dfs(m, n, i - 1, j, k);
            dfs(m, n, i + 1, j, k);
            dfs(m, n, i, j - 1, k);
            dfs(m, n, i, j + 1, k);
        }
    
        private int calc(int i, int j) { 
            String si = String.valueOf(i);
            String sj = String.valueOf(j);
            char[] c1 = si.toCharArray();
            char[] c2 = sj.toCharArray();
            int s = 0;
            for (char c : c1) { 
                s += c - 48;
            }
            for (char c : c2) { 
                s += c - 48;
            }
            return s;
        }
    }

[6a0e57cf45346791eee10cd3e2c056dc.png]: /images/20221014/2895b298472b47b1accf38fdce54292f.png
[a7982018cfb4033f1d2111f675713e1f.png]: /images/20221014/f02469ae51864fd9a1e7557a949e9414.png
[48791728f3f42c9a9adda30686be7a4e.png]: /images/20221014/77454a9d498247ac93cd021f2e3d26c3.png
[7ed122a1877055ce152f7d8bcff01400.png]: /images/20221014/08fd1f2431c94aa782382b2aa6108ef5.png
[b6e536fea39fe370282a734c844e7816.png]: /images/20221014/627facba8323477f93a8ab9feb7332ff.png
[c397b7a4efc3b713d3d4b31333a003aa.png]: /images/20221014/a3e2b86b44b1474997cbdadba3a0b2d6.png
[ea2491e0357b9b3e25073b16babb5301.png]: /images/20221014/c9a05ae272fa43df964f4ee7e705560e.png
[e6a7aedf9ce0d3e6f19db828e223f937.png]: /images/20221014/61d2d4ada0d14ac192944c04e6740542.png
[3736a76bbe2d2cc0a744926d621d914f.png]: /images/20221014/bec206fa4e8b466a8755eb60094c6c83.png
[a2bf050644f14649904af39a602f4727.png]: /images/20221014/189163e6744c418dad9794f5853dabb4.png
[46.]: https://leetcode-cn.com/problems/permutations/
[43c405bbda4b74195e5b95fbbdf62b47.png]: /images/20221014/563755b4051f4ba2b560b44d76a8b1f3.png
[10d535d7f9fa07f978047dd57d69252a.png]: /images/20221014/d4e24616b6084bbc88aa39cb0081112d.png
[a7e8be41487000d45e538e93eb52aef9.png]: /images/20221014/3c2b2911d788410ba03f8c72ca83243f.png
[Offer 12.]: https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/