爱上算法，迷人的两度搜索，爱上算法，迷人的两度搜索，深度优先（DFS）和 ...

迷人的两度搜索

1、BFS和DFS

深度优先搜索算法（DFS）和广度优先搜索算法（BFS）是一种用于遍历或搜索树或图的算法，在搜索遍历的过程中保证每个节点（顶点）访问一次且仅访问一次，按照节点（顶点）访问顺序的不同分为深度优先和广度优先。
1.1、深度优先搜索算法

深度优先搜索算法（Depth-First-Search，DFS）沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

注意：
1：实际上，回溯算法思想就是借助于深度优先搜索来实现的。
DFS负责搜索所有的路径，回溯辅以选择和撤销选择这种思想寻找可能的解，当然代码写起来基于递归（所以代码写起来就是用递归实现的）。
2：DFS跟回溯有什么关系呢？
回溯是一种通用的算法，把问题分步解决，在每一步都试验所有的可能，当发现已经找到一种方式或者目前这种方式不可能是结果的时候，退回上一步继续尝试其他可能（有一个选择和撤销选择的过程，可理解为标记访问和删除访问标记）。很多时候每一步的处理都是一致的，这时候用递归来实现就很自然。
当回溯(递归)用于树(图)的时候，就是深度优先搜索。当然了，几乎所有可以用回溯解决的问题都可以表示为树。（像之前的排列，组合等问题，虽不是直接在树上操作，但是他们操作的中间状态其实是一棵树）那么这俩在这里就几乎同义了。如果一个问题解决的时候显式地使用了树或图，那么我们就叫它dfs。很多时候没有用树我们也管它叫dfs严格地说是不对的，但是dfs比回溯打字的时候好输入。

DFS代码参考模板：

1. //Java
2. private void dfs(TreeNode root,int level,List<List<Integer>> results){
3.     //terminal 已下探到最底部节点
4.     if(results.size()==level){ // or root == null or node alread visited
5.         results.add(new ArrayList<>());
6.         return；
7.     }
8.     // process current level node here.
9.     results.get(level).add(root.val); // 记录当前节点已被访问
10.    
11.     //drill down   if node not visited
12.     if(root.left!=null){
13.         dfs(root.left,level+1,results);
14.     }
15.     if(root.right!=null){
16.         dfs(root.right,level+1,results);
17.     }
18. }

复制代码

是不是觉得跟二叉树的前中后序遍历很像，其实二叉树的前中后序遍历就是一种DFS，只不过记录节点的时机不一样而已。

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

1. //Java
2. public void dfs(Node node,List<Integer> res) {
3.     //terminal
4.     if (node == null) {
5.         return;
6.     }
7.     //process current level logic
8.     res.add(node.val);
9.     //drill down
10.     List<Node> children = node.children;
11.         for (Node n:children) {
12.             // if node not visited  then dfs node
13.             if (not visited) { // 在基于图的dfs中一般需要判断顶点是否已访问过
14.                 dfs(n,res);
15.             }
16.         }
17. }

复制代码

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

针对图的深度优先搜索算法，思路是一致的：

假设：从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）

1. //Java
2. public class TreeNode {
3.     int val;
4.     TreeNode left;
5.     TreeNode right;
7.     TreeNode(int x) {
8.         val = x;
9.     }
10. }
12. public List<List<Integer>> levelOrder(TreeNode root) {
13.     List<List<Integer>> allResults = new ArrayList<>();
14.     if (root == null) {
15.         return allResults;
16.     }
17.     Queue<TreeNode> nodes = new LinkedList<>();
18.     //将根节点入队列
19.     nodes.add(root);
20.     while (!nodes.isEmpty()) {
21.         //每次循环开始时：队列中的元素的个数其实就是当前这一层节点的个数
22.         int size = nodes.size();
23.         List<Integer> results = new ArrayList<>();
24.         for (int i = 0; i < size; i++) {
25.             //从队列中取出每一个节点（取出这一层的每个节点）
26.             TreeNode node = nodes.poll();
27.             results.add(node.val);
28.             //将该节点的左右子节点入队列
29.             if (node.left != null) {
30.                 nodes.add(node.left);
31.             }
32.             if (node.right != null) {
33.                 nodes.add(node.right);
34.             }
35.         }
36.         allResults.add(results);
37.     }
38.     return allResults;
39. }

复制代码

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

在图中的广度优先搜索过程如下：

参考该网址上的演示过程：https://visualgo.net/zh/dfsbfs
​
应用特点：
1：BFS适合在树或图中求解最近，最短等相关问题
2：DFS适合在树或图中求解最远，最深等相关问题
3：实际应用中基于图的应用居多
2、面试实战

102. 二叉树的层序遍历

滴滴，美团点评，腾讯最近面试题，102. 二叉树的层序遍历
典型的BFS，借助队列FIFO特性，

1. class Solution {
2.     public List<List<Integer>> levelOrder(TreeNode root) {
3.         //特殊判断
4.         if (root == null) {
5.             return new ArrayList();
6.         }
7.         Queue<TreeNode> queue = new LinkedList();
8.         queue.offer(root);
9.         List<List<Integer>> res = new ArrayList();
10.         while (!queue.isEmpty()) {
11.             int size = queue.size();
12.             List<Integer> list = new ArrayList();
13.             for (int i=0;i<size;i++) {
14.                 TreeNode poll = queue.poll();
15.                 list.add(poll.val);
17.                 //将左右子树节点加入队列
18.                 if (poll.left != null) {
19.                     queue.offer(poll.left);
20.                 }
21.                 if (poll.right != null) {
22.                     queue.offer(poll.right);
23.                 }
24.             }
25.             res.add(list);
26.         }
27.         return res;
28.     }
29. }

复制代码

104. 二叉树的最大深度

嘀嘀打车，百度最近面试题，104. 二叉树的最大深度
如果我们知道了左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为

1. class Solution {
2.     public List<List<Integer>> levelOrder(TreeNode root) {
3.         List<List<Integer>> res = new ArrayList();
4.         dfs(root,0,res);
5.         return res;
6.     }
8.     public void dfs(TreeNode root,int level,List<List<Integer>> res) {
9.         //terminal
10.         if (root==null) {
11.             return;
12.         }
13.         
14.         //将当前层的集合初始化好
15.         int size = res.size();
16.         if ( level > size-1) {
17.             res.add(new ArrayList());
18.         }
19.         //将当前节点加到当前层对应的集合中
20.         List<Integer> list = res.get(level);
21.         list.add(root.val);
23.         //drill down
24.         dfs(root.left,level+1,res);
25.         dfs(root.right,level+1,res);
27.     }
28. }

复制代码

而左子树和右子树的最大深度又可以以同样的方式进行计算。因此使用递归
其实这也是DFS的体现，直接下探到最深处得到最大深度，然后左右两边比较即可。

1. max(l,r)+1

复制代码

时间复杂度：O(n)，其中 n 为二叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度：O(height)，其中height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

进阶：能否用BFS完成
利用一个计数器，每遍历完一层就计一个数，直到所有层都遍历结束
[code]class Solution {    public int maxDepth(TreeNode root) {        //特殊判断        if (root==null) {            return 0;        }        Queue queue = new LinkedList();        queue.add(root);        int deep = 0;        while (!queue.isEmpty()) {            int size  = queue.size();            for (int i=0;i