刷题训练之深搜（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);
        }
    }

原文地址：https://blog.csdn.net/chaodddddd/article/details/143841285

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！