leetcode习题分类汇总- DFS、BFS篇

Maximum Depth of Binary Tree-返回二叉树的最大深度

思路:

(1)level order triversal,层级遍历,迭代,BFS

(2)递归,返回左右子树中较大的子树长度,DFS




### Same Tree-判断两个数是否相等

思路:DFS,不断判断左右子树是否相同






### Populating Next Right Pointers in Each Node-完全二叉树连接每个右边的节点

思路:迭代,BFS,设置levelstart/cur 两个指针层级遍历??难道是DFS??




### Convert Sorted Array to Binary Search Tree-有序数组转化为二叉搜索树

思路:DFS递归,二分法




### Balanced Binary Tree-判断是否为平衡二叉树

思路:DFS递归,不断比较当前左右子树深度是否<=1




### Symmetric Tree-判断是否对称

思路:DFS递归or迭代,递归代码好写点




### Sum Root to Leaf Numbers-计算路径的和

思路:递归或迭代,DFS传值累加,迭代容器选择queue




### Path Sum-判断路径是否存在和为sum值

思路:同上,DFS传值,不断减去当前值



Minimum Depth of Binary Tree-二叉树的最小深度
思路:BFS,维护level,DFS,维护最小值



### Binary Tree Right Side View-返回左侧值的列表

思路:还是DFS,发现没什么好说的了…






### Flatten Binary Tree to Linked List-二叉树展开为链表

思路:DFS,中左右遍历










### Binary Tree Maximum Path Sum

思路:


1) Recursively solve this problem
2) Get largest left sum and right sum
2) Compare to the stored maximum








### Recover Binary Search Tree-恢复一颗有两个元素调换错了的二叉查找树

思路:利用二叉查找树的主要性质,就是中序遍历是有序的性质。那么如果其中有元素被调换了,意味着中序遍历中必然出现违背有序的情况。那么会出现几次呢?有两种情况,如果是中序遍历相邻的两个元素被调换了,很容易想到就只需会出现一次违反情况,只需要把这个两个节点记录下来最后调换值就可以;
如果是不相邻的两个元素被调换了,举个例子很容易可以发现,会发生两次逆序的情况,那么这时候需要调换的元素应该是第一次逆序前面的元素,和第二次逆序后面的元素。比如1234567,1和5调换了,会得到5234167,逆序发生在52和41,我们需要把4和1调过来,那么就是52的第一个元素,41的第二个元素调换即可。
搞清楚了规律就容易实现了,中序遍历寻找逆序情况,调换的第一个元素,永远是第一个逆序的第一个元素,
而调换的第二个元素如果只有一次逆序,则是那一次的后一个,如果有两次逆序则是第二次的后一个。算法只需要一次中序遍历,所以时间复杂度是O(n),空间是栈大小O(logn)。


Construct Binary Tree from Inorder and Postorder Traversal-已知中序和后序遍历构造BT

思路:利用中序遍历的左中右和post的左右中,不断切分,map建立索引,dfs可以得出当前节点的左右子树,相当于一次树的遍历,时间N,空间N;



### Construct Binary Tree from Preorder and Inorder Traversal已知前序和中序遍历构造BT

思路:一样吧…利用中序遍历的左中右和pre的中左右,不断切分,map建立索引,dfs可以得出当前节点的左右子树,相当于一次树的遍历,时间N,空间N,这样的题目多练习就好。




### Clone Graph-无向图的复制



思路:图的复制,基于BFS,用到了Hashtable来去重

参考:
图的遍历有两种方式,BFS和DFS

这里使用BFS来解本题,BFS需要使用queue来保存neighbors

但这里有个问题,在clone一个节点时我们需要clone它的neighbors,而邻居节点有的已经存在,有的未存在,如何进行区分?

这里我们使用Map来进行区分,Map的key值为原来的node,value为新clone的node,当发现一个node未在map中时说明这个node还未被clone,

将它clone后放入queue中处理neighbors。

使用Map的主要意义在于充当BFS中Visited数组,它也可以去环问题,例如A–B有条边,当处理完A的邻居node,然后处理B节点邻居node时发现A已经处理过了

处理就结束,不会出现死循环!

queue中放置的节点都是未处理neighbors的节点!!!!



### Number of Islands-0,1代表水和陆地,求陆地数量。

思路:
DFS、BFS。只要遍历一遍,碰到一个1,就把它周围所有相连的1都标记为非1
,这样整个遍历过程中碰到的1的个数就是所求解。



### Course Schedule-根据课程的前后判断是否可能修完

思路:
本质是判断有向图中有没有闭环,DFS。

需要建立有向图,还是用二维数组来建立,和BFS不同的是,我们像现在需要一个一维数组visit来记录访问状态,
大体思路是,先建立好有向图,然后从第一个门课开始,找其可构成哪门课,暂时将当前课程标记为已访问,然后对新得到的课程调用DFS
递归,直到出现新的课程已经访问过了,则返回false,没有冲突的话返回true,然后把标记为已访问的课程改为未访问



### Course Schedule II-根据课程前后返回可行的上课顺序

思路:拓扑排序



### Binary Tree Level Order Traversal-二叉树的层级遍历

思路:设置levellast指针,用queue存储遍历,BFS




### Binary Tree Level Order Traversal II-bottom-up的层级遍历

思路:和之前一样,用addfirst()就可以。



 


### Surrounded Regions-把围棋围起来的部分消灭掉

思路:
BFS。对于每一个O,扫描其相邻节点,然后标示之,如果一个联通区域中有任何一个O在边界上,
则保留之,否则清除该联通域。
小数据可以过,但是大数据提示Memory Limit Exceeded,代码中唯一用到的就是visited这个map,所以,系统期望的方法应该是不需要辅助空间的。

转换一下思路,真的需要开辟一个map在存储访问信息吗?其实这个可以省掉的,既然已经知道连通区域必须至少一个元素是在四边,那么一开始直接从四边开始扫描就好了,所以无法connect到得元素都是应该被清除的。所以,算法如下:
1. 从四条边上的O元素开始BFS,所有相连的O都赋个新值,比如‘Y’
2. 扫描整个数组,所有现存的O元素全部置为X,所有Y元素置为O

这个思路是从边缘向内部找连通的‘O’的,所以DFS时,就没必要在判断边缘上的字母了,因此DFS中,i 和 j 的条件为:i > 1, i < row - 2; j > 1, j < col - 2。(为什么?如果是 i = 1 时,那么 dfs(board, i - 1,
j) 就是判断 [0, j] 了,而而边缘上的字母会被遍历判断的,这样就重复判断了,会导致栈溢出)。

DFS递归太深,容易栈溢出,这个代码可谓险过,最好还是用BFS。

Flood Fill方法的运用





总结:DFS,BFS主要用于树,图,矩阵的扫描,主要需要分清两者的应用情况和局限,其他需要了解一些常用的如Flood fill,KPM算法。这些题目一般思路清晰,但是容易出错。