【深搜算法】（第六篇）
目录
⼆叉树的所有路径（easy）
题目解析
讲解算法原理
编写代码
全排列（medium）
题目解析
讲解算法原理
编写代码
⼆叉树的所有路径（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个⼆叉树的根节点root，按任意顺序，返回所有从根节点到叶⼦节点的路径。叶⼦节点是指没有⼦节点的节点。
• ⽰例1：
输⼊：root=[1,2,3,null,5]
输出：["1->2->5","1->3"]
• ⽰例2：
输⼊：root=[1]
输出：["1"]
• 提⽰：
树中节点的数⽬在范围[1,100]内-100<=Node.val<=100
讲解算法原理
解法（回溯）：算法思路：
使⽤深度优先遍历（DFS）求解。路径以字符串形式存储，从根节点开始遍历，每次遍历时将当前节点的值加⼊到路径中，如果该节点
为叶⼦节点，将路径存储到结果中。否则，将"->"加⼊到路径中并递归遍历该节点的左右⼦树。定义⼀个结果数组，进⾏递归。递归具体实现⽅法如下：
1. 如果当前节点不为空，就将当前节点的值加⼊路径path中，否则直接返回；
2. 判断当前节点是否为叶⼦节点，如果是，则将当前路径加⼊到所有路径的存储数组paths中；
3. 否则，将当前节点值加上"->"作为路径的分隔符，继续递归遍历当前节点的左右⼦节点。
4. 返回结果数组。
• 特别地，我们可以只使⽤⼀个字符串存储每个状态的字符串，在递归回溯的过程中，需要将路径中的当前节点移除，以回到上⼀个节点。
具体实现⽅法如下：
1. 定义⼀个结果数组和⼀个路径数组。2. 从根节点开始递归，递归函数的参数为当前节点、结果数组和路径数组。
a. 如果当前节点为空，返回。
b. 将当前节点的值加⼊到路径数组中。
c. 如果当前节点为叶⼦节点，将路径数组中的所有元素拼接成字符串，并将该字符串存储到结果数组中。
d. 递归遍历当前节点的左⼦树。
e. 递归遍历当前节点的右⼦树。
f. 回溯，将路径数组中的最后⼀个元素移除，以返回到上⼀个节点。
3. 返回结果数组。
编写代码
c++算法代码：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
right(right) {}* };*/
class Solution
{
public:vector<string> ret; // 记录结果vector<string> binaryTreePaths(TreeNode* root) {string path;if(root == nullptr) return ret;dfs(root, path);return ret;}void dfs(TreeNode* root, string path){path += to_string(root->val);if(root->left == nullptr && root->right == nullptr){ret.push_back(path);return;}path += "->";if(root->left) dfs(root->left, path);if(root->right) dfs(root->right, path);}
};java算法代码：
/*** 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
{List<String> ret;public List<String> binaryTreePaths(TreeNode root) {ret = new ArrayList<>();dfs(root, new StringBuffer());return ret;}void dfs(TreeNode root, StringBuffer _path){StringBuffer path = new StringBuffer(_path);path.append(Integer.toString(root.val));if(root.left == null && root.right == null){ret.add(path.toString());return;}path.append("->");if(root.left != null) dfs(root.left, path);if(root.right != null) dfs(root.right, path);}
}全排列（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个不含重复数字的数组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中的所有整数互不相同
讲解算法原理
解法：
算法思路：
典型的回溯题⽬，我们需要在每⼀个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的⽅式，不断地枚举每个数在当前位置的可能性，并回溯到上⼀个状态，直到枚举完所有可能性，得到正确的结果。
每个数是否可以放⼊当前位置，只需要判断这个数在之前是否出现即可。具体地，在这道题⽬中，我们可以通过⼀个递归函数backtrack和标记数组visited来实现全排列。
递归函数设计：voidbacktrack(vector<vector<int>>&res,vector<int>&nums,vector<bool>&visited,vector<int>&ans,intstep,intlen)
参数：step（当前需要填⼊的位置），len（数组⻓度）；返回值：⽆；
函数作⽤：查找所有合理的排列并存储在答案列表中。
递归流程如下：
1. ⾸先定义⼀个⼆维数组res⽤来存放所有可能的排列，⼀个⼀维数组ans⽤来存放每个状态的排列，⼀个⼀维数组visited标记元素，然后从第⼀个位置开始进⾏递归；
2. 在每个递归的状态中，我们维护⼀个步数step，表⽰当前已经处理了⼏个数字；
3. 递归结束条件：当step等于nums数组的⻓度时，说明我们已经处理完了所有数字，将当前数组存⼊结果中；
4. 在每个递归状态中，枚举所有下标i，若这个下标未被标记，则使⽤nums数组中当前下标的元
素：
a. 将visited[i]标记为1；
b. ans数组中第step个元素被nums[i]覆盖；
c. 对第step+1个位置进⾏递归；
d. 将visited[i]重新赋值为0，表⽰回溯；
5. 最后，返回res。
• 特别地，我们可以不使⽤标记数组，直接遍历step之后的元素（未被使⽤），然后将其与需要递归的位置进⾏交换即可。
编写代码
c++算法代码：
class Solution
{vector<vector<int>> ret;vector<int> path;bool check[7];
public:vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}void dfs(vector<int>& nums){if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(!check[i]){path.push_back(nums[i]);check[i] = true;dfs(nums);// 回溯 -> 恢复现场path.pop_back();check[i] = false;}}}
};java算法代码：
class Solution
{List<List<Integer>> ret;List<Integer> path;boolean[] check;public List<List<Integer>> permute(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];dfs(nums);return ret;}public void dfs(int[] nums){if(nums.length == path.size()){ret.add(new ArrayList<>(path));return;}for(int i = 0; i < nums.length; i++){if(check[i] == false){path.add(nums[i]);check[i] = true;dfs(nums);// 回溯 -> 恢复现场check[i] = false;path.remove(path.size() - 1);}}}
}