1、BFS和DFS深度优先搜索算法（DFS）和广度优先搜索算法（BFS）是一种或者搜索树或者图的算法，在搜索遍历的过程中，保证每个节点（顶点）被访问一次且仅访问一次，按照顺序分为深度优先和广度优先节点（顶点）访问。1.1.Depth-FirstSearchAlgorithmDepth-First-Search(DFS)沿着树的深度遍历树的节点，尽可能深地搜索树的分支。探索完节点v的所有边后，搜索将回溯到找到节点v的边的起始节点。这个过程一直持续到找到所有从源节点可达的节点。如果还有未发现的节点，则选择其中一个作为源节点，重复上述过程，重复整个过程，直到访问完所有节点。属于盲目搜索。注：1：其实回溯算法的思想是通过深度优先搜索的方式实现的。DFS负责搜索所有路径，回溯辅以选择和取消选择的思想寻找可能的解。当然，代码是基于递归写的（所以代码是用递归写的）。2：DFS和回溯有什么关系？回溯是一种通用的算法，它一步步解决问题，并在每一步都尝试所有的可能性。当发现已经找到一个方法或者当前方法不能是结果时，回到上一步继续尝试其他可能（有一个选择和取消选择的过程，可以理解为标记访问和移除访问标记）。很多时候，每一步的处理都是一致的，这时候自然要用递归来实现。当在树（图）上使用回溯（递归）时，它是深度优先搜索。当然，几乎任何可以使用回溯法解决的问题都可以表示为一棵树。（虽然排列组合等问题并没有直接对树进行操作，但是它们操作的中间状态其实就是一棵树。）那么这两个在这里几乎是同义词。如果使用树或图显式解决问题，则我们将其称为dfs。很多时候我们不使用树，我们称它为dfs。严格来说是错误的，但是dfs比backtracking更容易打字。DFS代码参考模板：//Javaprivatevoiddfs(TreeNoderoot,intlevel,List>results){//终端已经到达底部节点if(results.size()==level){//或者root==nullornodealreadyvisitedresults.add(newArrayList<>());返回;}//在此处处理当前级别节点.results.get(level).add(root.val);//记录当前节点是否访问过//如果节点未访问则向下钻取if(root.left!=null){dfs(root.left,level+1,results);}if(root.right!=null){dfs(root.right,level+1,results);}}是不是觉得很像二叉树的前中后序遍历？二叉树的前中后序遍历其实也是一种DFS，只是记录节点的时机不同而已。对于多树DFS，代码参考模板如下：//Javapublicvoiddfs(Nodenode,Listres){//terminalif(node==null){return;}//处理当前级别的逻辑res.添加（节点.val）；//向下钻取Listchildren=node.children;for(Noden:children){//ifnodenotvisitedthendfsnodeif(notvisited){//在graph-baseddfs中，一般需要判断顶点是否已经被dfs(n,res访问过));当然我们也可以自己用栈来模拟递归过程，将递归代码改写成非递归代码！对于图的深度优先搜索算法，思路是一样的：假设：从S开始搜索，每次搜索都是先到最底下，再往回走。比如：S->A->D->G->E->B，到最后，再回到G，再到最后，S->A->D->G->F->C1。2.广度优先搜索算法Breadth-First-Search(BFS)直观上看，其实是一种逐层推进的“地毯式”搜索策略，即先找到离起始顶点最近的，然后再将它次之，依次向外寻找。简单的说，BFS从根节点开始，沿着树（graph）的宽度遍历树（graph）的节点。如果访问完所有节点，则算法终止，队列数据结构一般用于辅助实现BFS算法。犹如一滴水滴在湖面上，顿时泛起了波纹！周边展开dfs和bfs搜索方式的比较：BFS代码参考模板：需要用到队列Queue（或Deque）//JavapublicclassTreeNode{intval;树节点离开；树节点对；TreeNode(intx){val=x;}}publicList>levelOrder(TreeNoderoot){List>allResults=newArrayList<>();if(root==null){返回所有结果；}Queuenodes=newLinkedList<>();//将根节点加入队列nodes.add(root);while(!nodes.isEmpty()){//每次循环开始时：队列中的元素个数实际为当前层的节点个数intsize=nodes.size();List结果=newArrayList<>();for(inti=0;i>levelOrder(TreeNoderoot){//特殊判断if(root==null){returnnewArrayList();}队列queue=newLinkedList();queue.offer（根）；列表<列表<整数>>res=newArrayList();while(!queue.isEmpty()){intsize=queue.size();Listlist=newArrayList();for(inti=0;i>res){//terminalif(root==null){return;}//初始化当前图层的集合intsize=res.size();if(level>size-1){res.add(newArrayList());}//将当前节点添加到当前层对应的集合中Listlist=res.get(level);list.add(root.val);//向下钻取dfs(root.left,level+1,res);dfs(root.right,level+1,res);}}104。二叉树的最大深度滴滴打车，百度最近的面试题，104二叉树的最大深度如果我们知道左子树和右子树的最大深度l和r，那么二叉树的最大深度就是max(l,r)+1和左右子树的最大深度可以同理计算。所以，使用递归其实就是DFS的一种体现。可以直接钻到最深点，得到最大深度，然后左右对比。类解决方案{publicintmaxDepth(TreeNoderoot){returndfs(root);}//求一棵子树的最大深度publicintdfs(TreeNodenode){//终止条件if(node==null){return0;}//左子树的最大深度intleftDepth=dfs(node.left);//右子树的最大深度intrightDepth=dfs(node.right);//当前节点的最大深度为左子树的最大深度和右子树最大深度中的最大值+1returnMath.max(leftDepth,rightDepth)+1;}}时间复杂度：O(n)，其中n是二叉树节点的数量。每个节点在递归中只遍历一次。空间复杂度：O(height)，其中height表示二叉树的高度。递归函数需要栈空间，而栈空间又取决于递归的深度，所以空间复杂度相当于一棵二叉树的高度。进阶：BFS能否完成一个计数器的使用，每遍历一层就计数一个数，直到遍历完所有层classSolution{publicintmaxDepth(TreeNoderoot){//特殊判断if(root==null){返回0;}队列queue=newLinkedList();queue.add（根）；深=0；while(!queue.isEmpty()){intsize=queue.size();for(inti=0;ilargestValues(TreeNoderoot){Listres=new数组列表（）;如果(root==null){返回res;}队列queue=newLinkedList();queue.offer（根）；while(!queue.isEmpty()){intsize=queue.size();intmax=Integer.MIN_VALUE;for(inti=0;i=0&&x=0&&y
