【深搜算法】(第六篇)
目录
⼆叉树的所有路径(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);}}}
}