刷题训练之深搜（DFS）-----（二叉树的所有路径，全排列，子集）

二叉树的所有路径

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。

题目分析：

题目要我们找到一个课的所有路径，就是要找到从根节点到每一个叶子节点的路径

终止条件就是当遇到叶子节点的时候用一个全局变量ret接收它此时的路径并且返回给它上一次的路径

例如 拿节点5举例此时它还不为叶子节点所以它需要继续往左树和右数寻找 此时找到叶子节点 1->2->5->7 得返回1->2->5回去（但是此题目可以省略，可以设计函数的时候直接传入俩个值）

dfs（root，path） 此时path为当前路径

此题目需要频繁要在字符串后面添加字符“->” 可以使用 StringBuffer 可以自由在后面添加

class Solution {List<String> ret = new ArrayList<>();public List<String> binaryTreePaths(TreeNode root) {dfs(root,new StringBuffer());return ret;}public void dfs(TreeNode root,StringBuffer s) {StringBuffer path = new StringBuffer(s);if(root == null) {return;}path.append(Integer.toString(root.val));if(root.left == null && root.right == null) {ret.add(path.toString());return ;}path.append("->");dfs(root.left,path);dfs(root.right,path);}
}

全排列

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

题目分析：

全排序：将一组数字以不同的顺序组合起来，一组数字里面不能重复使用，看看能有多少种

先判断何为出口？

当遇到叶子节点时候，使用全局变量ret直接添加结果

此时的叶子节点相当于路径path的大小是否等于数组的大小

细节：

因为不能使用重复的数字，所有需要一个Boolean数组来记录它们的状态如果使用了将它记录为true（已使用）

回溯：

当添加完后，返回给上一层时候，需要把path最后一个数字删除，并且恢复改数字的状态为false（未使用）

dfs(nums)

函数体：仅需要关注某个节点做了什么事情

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;}void dfs(int[] nums) {if(path.size() == nums.length) {ret.add(new ArrayList<>(path));}for(int i = 0;i<nums.length;i++) {if(check[i] == false) {path.add(nums[i]);check[i] = true;dfs(nums);path.remove(path.size()-1);check[i] = false;}}}
}

子集

给你一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的

子集（幂集）。

解集不能包含重复的子集。你可以按任意顺序返回解集。

题目分析：

×代表不选 √代表选择

此题目可以抽象成 选和不选 俩种情况看待

1.选直接添加到path路径并且进入下一次递归回退过程中并且删除最后一个数字

2.不选直接递归

设计函数头 dfs（nums，index）

index标记此时在nums中哪个数字

终止条件：

当遇到到叶子节点的时候 用一个全局变量ret接收

当 index == 数组长度时，可以发现它就是最后一个节点了

class Solution {List<List<Integer>> ret = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {dfs(nums,0);return ret;}void dfs(int[] nums,int index) {if(index == nums.length) {ret.add(new ArrayList<>(path));return ;}//不选dfs(nums,index+1);//选path.add(nums[index]);dfs(nums,index+1);path.remove(path.size()-1);}
}

解法二：

函数头设计 dfs（nums，index）

此时的递归出口将三个数字遍历完成就行

何时添加到ret中？

一进入到dfs中，就可以一直添加path

    List<List<Integer>> ret = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {dfs(nums,0);return ret;}void dfs(int[] nums,int index) {ret.add(new ArrayList<>(path));for(int i = index;i<nums.length;i++) {path.add(nums[i]);dfs(nums,i+1);path.remove(path.size()-1);}}