迷人的两度查找

本文正在参与「金石方案 . 分割6万现金大奖」

1、BFS和DFS

深度优先查找算法（DFS）和广度优先查找算法（BFS）是一种用于遍历或查找树或图的算法，在查找遍历的进程中保证每个节点（极点）拜访一次且仅拜访一次，依照节点（极点）拜访次序的不同分为深度优先和广度优先。

1.1、深度优先查找算法

深度优先查找算法（Depth-First-Search，DFS）沿着树的深度遍历树的节点，尽或许深的查找树的分支。当节点v的所在边都己被探寻过，查找将回溯到发现节点v的那条边的开端节点。这一进程一直进行到已发现从源节点可达的一切节点为止。假如还存在未被发现的节点，则挑选其间一个作为源节点并重复以上进程，整个进程重复进行直到一切节点都被拜访为止。属于盲目查找。

注意：

1：实践上，回溯算法思维便是凭借于深度优先查找来完结的。

DFS担任查找一切的途径，回溯辅以挑选和撤销挑选这种思维寻觅或许的解，当然代码写起来根据递归（所以代码写起来便是用递归完结的）。

2：DFS跟回溯有什么关系呢？

回溯是一种通用的算法，把问题分步处理，在每一步都实验一切的或许，当发现现已找到一种方法或者现在这种方法不或许是成果的时分，退回上一步继续尝试其他或许（有一个挑选和撤销挑选的进程，可理解为符号拜访和删除拜访符号）。许多时分每一步的处理都是共同的，这时分用递归来完结就很自然。

当回溯(递归)用于树(图)的时分，便是深度优先查找。当然了，简直一切可以用回溯处理的问题都可以表示为树。（像之前的排列，组合等问题，虽不是直接在树上操作，可是他们操作的中间状态其实是一棵树）那么这俩在这里就简直同义了。假如一个问题处理的时分显式地运用了树或图，那么咱们就叫它dfs。许多时分没有用树咱们也管它叫dfs严格地说是不对的，可是dfs比回溯打字的时分好输入。

DFS代码参阅模板：

//Java
private void dfs(TreeNode root,int level,List<List<Integer>> results){
    //terminal 已下探到最底部节点
    if(results.size()==level){ // or root == null or node alread visited
        results.add(new ArrayList<>()); 
        return；
    }
    // process current level node here.
    results.get(level).add(root.val); // 记载当时节点已被拜访
    //drill down   if node not visited
    if(root.left!=null){
        dfs(root.left,level+1,results);
    }
    if(root.right!=null){
        dfs(root.right,level+1,results);
    }
}

是不是觉得跟二叉树的前中后序遍历很像，其实二叉树的前中后序遍历便是一种DFS，只不过记载节点的机遇不一样罢了。

针对多叉树的DFS，代码参阅模板如下：

//Java
public void dfs(Node node,List<Integer> res) {
    //terminal 
    if (node == null) {
        return;
    }
    //process current level logic
    res.add(node.val);
    //drill down 
    List<Node> children = node.children;
        for (Node n:children) {
            // if node not visited  then dfs node
            if (not visited) { // 在根据图的dfs中一般需要判别极点是否已拜访过
                dfs(n,res);
            }
        }
}

当然咱们也可以自己运用栈来模拟递归的进程，将递归代码改写成非递归代码！

针对图的深度优先查找算法，思路是共同的：

假定：从S开端进行查找，每次查找，先一头扎究竟，然后再回退，回退进程中有其他路再一头扎究竟。比方：S->A->D->G->E->B，究竟了，然后回退到G，再一头扎究竟，S->A->D->G->F->C

1.2、广度优先查找算法

广度优先查找算法（Breadth-First-Search，BFS）直观地讲，它其实便是一种“地毯式”层层推进的查找战略，即先查找离开端极点最近的，然后是次近的，依次往外查找。

简略的说，BFS是从根节点开端，沿着树(图)的宽度遍历树(图)的节点。假如一切节点均被拜访，则算法间断,一般用行列数据结构来辅助完结BFS算法。

就像在湖面上滴一滴水，构成的水波纹！向四周散开

dfs和bfs查找方法的比较：

BFS代码的参阅模板：需要凭借一个行列Queue（或Deque）

//Java
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) {
        val = x;
    }
}
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> allResults = new ArrayList<>();
    if (root == null) {
        return allResults;
    }
    Queue<TreeNode> nodes = new LinkedList<>();
    //将根节点入行列
    nodes.add(root);
    while (!nodes.isEmpty()) {
        //每次循环开端时：行列中的元素的个数其实便是当时这一层节点的个数
        int size = nodes.size();
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            //从行列中取出每一个节点（取出这一层的每个节点）
            TreeNode node = nodes.poll();
            results.add(node.val);
            //将该节点的左右子节点入行列
            if (node.left != null) {
                nodes.add(node.left);
            }
            if (node.right != null) {
                nodes.add(node.right);
            }
        }
        allResults.add(results);
    }
    return allResults;
}

就相当于刚开端把公司老总放入行列，这是第一层，然后把老总的直接下级比方：vp，总监等，取出来，然后放入行列，到了vp，总监这一层时，再把他们的直接部属放入行列。

在图中的广度优先查找进程如下：

参阅该网址上的演示进程：visualgo.net/zh/dfsbfs

​

运用特色：

1：BFS适合在树或图中求解最近，最短等相关问题

2：DFS适合在树或图中求解最远，最深等相关问题

3：实践运用中根据图的运用居多

2、面试实战

102. 二叉树的层序遍历

滴滴，美团点评，腾讯最近面试题，102. 二叉树的层序遍历

典型的BFS，凭借行列FIFO特性，

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        //特殊判别
        if (root == null) {
            return new ArrayList();
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        List<List<Integer>> res = new ArrayList();
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList();
            for (int i=0;i<size;i++) {
                TreeNode poll = queue.poll();
                list.add(poll.val);
                //将左右子树节点参加行列
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
            }
            res.add(list);
        }
        return res;
    }
}

时刻复杂度O(n)，空间复杂度O(n)

进阶：能否根据DFS完结

思路：依照深度优先遍历，遍历进程中将当时节点的值添加到它所对应的深度的调集中。因而需要一个在dfs进程中代表深度的变量

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList();
        dfs(root,0,res);
        return res;
    }
    public void dfs(TreeNode root,int level,List<List<Integer>> res) {
        //terminal
        if (root==null) {
            return;
        }
        //将当时层的调集初始化好
        int size = res.size();
        if ( level > size-1) {
            res.add(new ArrayList());
        }
        //将当时节点加到当时层对应的调集中
        List<Integer> list = res.get(level);
        list.add(root.val);
        //drill down
        dfs(root.left,level+1,res);
        dfs(root.right,level+1,res);
    }
}

104. 二叉树的最大深度

嘀嘀打车，百度最近面试题，104. 二叉树的最大深度

假如咱们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为

max(l,r)+1

而左子树和右子树的最大深度又可以以同样的方法进行核算。因而运用递归

其实这也是DFS的表现，直接下探到最深处得到最大深度，然后左右两头比较即可。

class Solution {
    public int maxDepth(TreeNode root) {
        return dfs(root);
    }
    //求一棵子树的最大深度
    public int dfs(TreeNode node) {
        //停止条件
        if (node == null) {
            return 0;
        }
        //左子树最大深度
        int leftDepth = dfs(node.left);
        //右子树最大深度
        int rightDepth = dfs(node.right);
        //当时节点的最大深度为左子树最大深度和右子树最大深度中的最大值+1
        return Math.max(leftDepth,rightDepth) +1;
    }
}

时刻复杂度：O(n)，其间 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。

空间复杂度：O(height)，其间height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因而空间复杂度等价于二叉树的高度。

进阶：能否用BFS完结

使用一个计数器，每遍历完一层就计一个数，直到一切层都遍历完毕

class Solution {
    public int maxDepth(TreeNode root) {
        //特殊判别
        if (root==null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        int deep = 0;
        while (!queue.isEmpty()) {
            int size  = queue.size();
            for (int i=0;i<size;i++) {
                TreeNode p = queue.poll();
                if (p.left!=null) {
                    queue.offer(p.left);
                }
                if (p.right!=null) {
                    queue.offer(p.right);
                }
            }
            //每一层节点遍历完结后计数器+1
            deep++;
        }
        return deep;
    }
}

小结：

在实践运用中，DFS要比BFS运用的广泛！

515. 在每个树行中找最大值

facebook，百度，字节面试题，515. 在每个树行中找最大值

典型的BFS

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList();
        if (root==null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            for (int i=0;i<size;i++) {
                TreeNode p = queue.poll();
                if (p.left !=null) {
                    queue.offer(p.left);
                }
                if (p.right!=null) {
                    queue.offer(p.right);
                }
                //比较判别每一层的最大值
                max = Math.max(max,p.val);
            }
            //保存每一层的最大值
            res.add(max);
        }
        return res;
    }
}

200. 岛屿数量

亚马逊，华为，字节最近面试题，很高频，200. 岛屿数量

典型的图的查找，立马想到DFS和BFS

class Solution {
    //界说极点向：上下左右，各走一步的方向信息
    int[][] directions = {{0,1},{0,-1},{-1,0},{1,0}};
    //界说网格的行数
    int rows;
    //界说网格的列数
    int clos;
    public int numIslands(char[][] grid) {
        //界说岛屿总数
        int count = 0;
        //获取网格有多少行
        rows = grid.length;
        if (rows==0) {
            return count;
        }
        //获取网格有多少列
        clos = grid[0].length;
        //界说网格各极点是否被拜访过
        boolean[][] visited = new boolean[rows][clos];
        //从图中去找能构成岛屿的极点
        for (int i=0;i<rows;i++) {
            for (int j=0;j<clos;j++) {
                //假如是陆地，并且没有被拜访过则深度优先查找(i,j)极点相连的陆地。
                if (grid[i][j] == '1' && !visited[i][j]) {
                    dfs(i,j,visited,grid);
                    //找到一块count+1
                    count++;
                }
            }
        }
        return count;
    }
	//查找与(x,y)相连的陆地极点，并符号这些极点。
    public void dfs(int x,int y,boolean[][] visited,char[][] grid) {
        //走过的极点要符号
        visited[x][y] = true;
        //从该极点，向上下左右四个方向去走
        for (int i=0;i< 4;i++) {
            int newX = x + directions[i][0]; // directions[i]别离代表上下左右四个方向 directions[i][0]是X轴坐标要走的距离
            int newY = y + directions[i][1];
            //假如新极点在网格内,且是陆地，且没有拜访过,则继续查找下去
            if (inGrid(newX,newY) && grid[newX][newY]=='1' && !visited[newX][newY]) {
                dfs(newX,newY,visited,grid);
            }
        }
    }
    //查看极点(x,y)是否在网格内
    public boolean inGrid(int x,int y) {
        return x>=0 && x< rows && y>=0 && y<clos;
    }
}

其他标题

127. 单词接龙

529. 扫雷游戏

36. 有效的数独

往期干货：

• Apache Druid数据查询套件详解计数、排名和分位数核算（送JSON-over-HTTP和SQL两种查询详解）

• 假如你还没玩过Docker Stack管理服务，你现已out了，（送Portainer集群管理教程）

• 怎样才能快速成为一名架构师？

• 怎么从Java工程师成长为架构师？

• 六种常用业务处理方案，你方唱罢，我登场（没有最好只要更好）

• 超具体教程，一文入门Istio架构原理及实战运用

• 【图解源码】Zookeeper3.7源码剖析，Session的管理机制，Leader选举投票规则，集群数据同步流程

• 【图解源码】Zookeeper3.7源码分析，包含服务启动流程源、网络通信、RequestProcessor处理请求

• 【知其然，知其所以然】装备中心 Apollo源码剖析

• 【推荐】我认为这是最完好的Apollo教程从入门到通晓

• 探针技能-JavaAgent 和字节码增强技能-Byte Buddy

• 100003字，带你解密 双11、618电商大促场景下的系统架构体系

• 【开悟篇】Java多线程之JUC从入门到通晓

• 12437字，带你深入探求RPC通讯原理

• JVM调优实战演练，妈妈再也不同忧虑我的功能优化了

• 13651个字，给你解释清楚 JVM目标毁掉

• 搞不懂JVM的类加载机制，JVM功能优化从何谈起？

• 4859字，609行，一次讲清楚JVM运转数据区

• 让实习生搭个Redis集群，差点把我”搭“进去~~~

• 我用Redis分布式锁，抢了瓶茅台，然后GG了~~

• 新来的，你说下Redis的持久化机制，哪一种能处理咱们遇到的这个业务问题？

本文由传智教育博学谷教研团队发布。

假如本文对您有帮助，欢迎关注和点赞；假如您有任何主张也可留言评论或私信，您的支撑是我坚持创作的动力。

转载请注明出处！