社区首页 >专栏 >刷题训练之深搜（DFS）-----（二叉树的所有路径，全排列，子集）

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

用户11369558

发布于 2024-11-20 07:12:22

12000

代码可运行

文章被收录于专栏：JavaJava

运行总次数：0

代码可运行

二叉树的所有路径

给你一个二叉树的根节点 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);
        }
    }