张家口百姓网:借助leetcode问题来领会BFS和DFS

2020-04-28 5 views 0

扫一扫用手机浏览

广度优先和深度优先搜索

前言

看着这两个搜索的条件的是读者具备图这一数据结构的基本知识,这些可以直接百度一波就了解了。图也像树一样,遍历具有许多的学问在内里,下面我将借用leetcode问题解说一下,虽然是图的遍历,然则借助树似乎讲的更见浅白一点,欠好的地方多指教。

广度优先搜索(BFS)

-对于树而言,就是一种层层遍历的感受,在实现的过程中,经常借助的是辅助行列来实现,也就是借助先进先出的特征来实现的。下图来看。用BFS的话,就是3-9-20-15-7的效果。

整体实现来说,就是遍历root再来遍历左右子树,不外与DFS区别的是,这里是借助先进先出的特点,也就是要将前面的先排列出来,不用走到叶子结点才输出。一句话简朴来说,BFS就是行列,入行列,出行列;

下面是借助leetcode的问题来牢固这个知识点,上面的图也是这个题的。问题要求层层从左往右遍历结点。

  class Solution {
        public int[] levelOrder(TreeNode root) {
            //特殊情况
            if(root == null){
                return neW int[0];
            }
            //用行列来实现广度优先搜索
            ArrayList&lT.I.teger> list = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while(!queue.isEmpty()){
                // 出列,这里的顺序就是先进先出,层层逐个遍历
                TreeNode node = queue.poll();
                list.add(node.val);
                // 逐个入列,辅助行列也是BFS的要害点
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.rIGht != null){
                    queue.add(node.right);
                }

            }
			// 这样转换会慢一点
            // int[] res = list.stream().mapToInt(Integer::valueOf).toArray();
            int[] res = new int[list.size()];
            for(int i = 0; i < list.size();i++){
                res[i] = list.get(i);
            }
            //问题要求返回的是int[]
            return res;



        }
    }


}

上面这道可以变形成输出效果不一样,也就是剑指offer中的后面两道-面试题31 - II. 从上到下打印二叉树和面试32题。

31题是要求输出的效果是差别数组的聚集,每层的结点作为一个数组,解决代码如下

class Solution {
    List<List<Integer>> res  = new LinkedList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
           if(root == null){
                return res;
            }
            //用行列来实现广度优先搜索      
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while(!queue.isEmpty()){
                ArrayList<Integer> list = new ArrayList<>();
                //用行列的长度来做,这里在for循环中,长度一直在变,以是要先将其取出来
                //要害点:主要头脑在于用每次的行列长度来 判断这一层的结点有若干
                //正如一最先只有一个根结点,以是长度即是一,只需执行一次添加list
                int size = queue.size();
                for(int i = 0; i < size; i++){
                // 出列,这里的顺序就是先进先出,层层逐个遍历
                TreeNode node = queue.poll();
                //这道题要求每层出一个数组
                list.add(node.val);
                // 逐个入列,辅助行列也是BFS的要害点
                if(node.left != null){ queue.add(node.left);}
                if(node.right != null){queue.add(node.right);}
                }
                //每层加完就添加到效果内里
                res.add(list);

            }
			
            //问题要求返回的是List<List<>>
            return res;



        }

    }

32题有和上面不一样的地方在于,第一行根据从左到右的顺序打印,第二层根据从右到左的顺序打印,第三行再根据从左到右的顺序打印,其他行以此类推。就是奇数偶数层不一样的遍历方式。可以通过借助一个布尔常量来实现。

class Solution {
  List<List<Integer>> res  = new LinkedList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
           if(root == null){
                return res;
            }
            //用行列来实现广度优先搜索      
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            boolean flag = true;
            while(!queue.isEmpty()){
                //这道题有实现头插法,为了高效,使用链表数组
                List<Integer> list = new LinkedList<>();
                //用行列的长度来做,这里在for循环中,长度一直在变,以是要先将其取出来
                int size = queue.size();
                for(int i = 0; i < size; i++){
                // 出列,这里的顺序就是先进先出,层层逐个遍历
                TreeNode node = queue.poll();
                //要害点:这道题要求每层出一个数组,而且奇数行和偶数不一样
                //奇数行是从左往右,偶数行是从右往左走
                //借助一个布尔类型来完成
                if(flag){
                    list.add(node.val);
                }else{
                    //前面最先插
                    list.add(0,node.val);
                }
                // 逐个入列,辅助行列也是BFS的要害点
                if(node.left != null){ queue.add(node.left);}
                if(node.right != null){queue.add(node.right);}
                }
				//每次遍历完一行便最先替换布尔类型
                flag = !flag;
                //每层加完就添加到效果内里
                res.add(list);

            }
			
            //问题要求返回的是List<List<>>a
            return res;

    }
}

深度优先搜索DFS

讲到DFS,很容易想到递归,没错它就是借助了递归的头脑。在图中的形貌是:深度优先搜索在搜索过程中接见某个极点后,需要递归地接见此极点的所有未接见过的相邻极点

上面的图即是该题,问题要求输入一个目的sum,打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点最先往下一直到叶节点所经由的节点形成一条路径。

 好比给出22,则返回下面
 {
 [5,4,11,2],
 [5,8,4,5]
 }
/**
leetcode 二叉树中和为某一值的路径(剑指offer34题)
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    LinkedList<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        // 有遍历 有递归
        recur(root,sum);
        //返回的是链表的链表效果
        return res;
    }

    public void recur(TreeNode root,int sum){
//        递归的终止条件
        if (root == null){
            return;
        }
        path.add(root.val);
        sum -= root.val;
        //找到了最后叶子结点,且可以知足sum的和要求,便将该效果添加进去res
        if (sum == 0&& root.left ==null&&root.right == null){
            //这里需要添加新的工具
            res.add(new LinkedList<>(path));
        }
//        左子树递归
        recur(root.left,sum);
//        右子树递归
        recur(root.right,sum);
//        删掉上一个结点,这一步是比较难明白的,这一步有点回溯的感受,就是你找到最后不符合要求的结点,你要返回到上一步,重新走下去。这一步是左右子树都递归完成后就会执行的
        path.removeLast();

    }
}

最后

这里的DFS还没讲完,只是单纯讲了这一道,后面再补上一些问题来写。

,

Sunbet 申博

申博Sunbet www.sunbet.xyz是Sunbet指定的Sunbet官网,Sunbet提供Sunbet(Sunbet)、Sunbet、申博代理合作等业务。

Sunbet内容转载自互联网,如有侵权,联系Sunbet删除。

本文链接地址:http://www.chongqichengbaotoy.com/post/1086.html

相关文章

发表评论