199. Binary Tree Right Side View

思路：想要得到樹(shù)的每一層最右側(cè)元素值，用BFS最方便。先訪問(wèn)左節(jié)點(diǎn)再訪問(wèn)右節(jié)點(diǎn)，最后訪問(wèn)的一個(gè)值就是留下的值。
想要DFS的思路也可以。只是一定要訪問(wèn)所有節(jié)點(diǎn)。

代碼

491 Increasing Subsequences

思路：我的習(xí)慣思維是對(duì)于nums[idx]可以選擇取或者不取。取的話，在什么條件下可以取。滿足什么條件的結(jié)果可以記錄到結(jié)果中。想好這些就能寫(xiě)代碼了。
本題：list記錄上一步已經(jīng)取的數(shù)字。如果if (list.size() == 0 || nums[idx] >= list.get(list.size()-1)) 的時(shí)候就可以取當(dāng)前元素到列表。只要list.size 大于等于2 就可以加入結(jié)果集。題目還需要去重。
學(xué)習(xí)：還有一種dfs的思路是：findSequence(int[] nums, int idx, Deque<Integer> list, Set<List<Integer>> result) 前一步放入list中的最后一個(gè)元素的下標(biāo)是idx-1，當(dāng)前可以決定繼續(xù)加入的元素是從idx到數(shù)組末尾中的任何一個(gè)元素，當(dāng)然元素也是要符合條件的。
代碼

785. Is Graph Bipartite?

思路：要把所有的頂點(diǎn)（下標(biāo)）分為兩個(gè)集合lista 和listb。先往lista加入節(jié)點(diǎn)0。和0相鄰的點(diǎn)加listb。再不斷遍歷lista和listb，加入新的節(jié)點(diǎn)。如果相鄰節(jié)點(diǎn)在同一個(gè)list中那就返回false。代碼啰嗦笨拙，參見(jiàn)isBipartiteV2。
學(xué)習(xí)1：用colors數(shù)組來(lái)區(qū)分兩個(gè)集合。-1認(rèn)為還沒(méi)有加顏色；0為一組；1為另外一組。在加顏色過(guò)程中使用DFS的思路。
例如輸入： [[1,3], [0,2], [1,3], [0,2]]。
染色順序：從0到1；從1到2；從2到3；3的鄰邊已經(jīng)染色完成，判斷是不是有效就行。
學(xué)習(xí)2：思路同上。在加顏色過(guò)程中使用BFS的思路。
例如輸入： [[1,3], [0,2], [1,3], [0,2]]。
染色順序：從0到1；從0到3；1,3加入隊(duì)列；一邊染色，一邊判斷是否有效；
從1到0，從1到2；2加入隊(duì)列；一邊染色，一邊判斷是否有效；
從3到0，從3到2；一邊染色，一邊判斷是否有效；
從2到1，從2到3；
代碼

129. Sum Root to Leaf Numbers

思路：深度優(yōu)先的套路。在處理每個(gè)當(dāng)前節(jié)點(diǎn)node的時(shí)候把它當(dāng)做根節(jié)點(diǎn)，繼續(xù)dfs；找到node與其根節(jié)點(diǎn)關(guān)系，再定返回值。
代碼

200. Number of Islands

思路：用DFS的思路很簡(jiǎn)單。找到一個(gè)島嶼的起點(diǎn)(i,j)，不斷向4個(gè)方向擴(kuò)散，把相鄰的節(jié)點(diǎn)都改為2。這樣一次完整的dfs遍歷算是一個(gè)島嶼識(shí)別完成。接著再找下個(gè)島嶼的起點(diǎn)。
學(xué)習(xí)：UnionFind并查集思路。將二維的grid，用一維數(shù)組表示父節(jié)點(diǎn)信息。
代碼

116. Populating Next Right Pointers in Each Node

思路：dfs的話，先遍歷一個(gè)節(jié)點(diǎn)的右子樹(shù)，在同一深度保持盡可能的右側(cè)節(jié)點(diǎn)。但是當(dāng)同一層的節(jié)點(diǎn)稱為別的節(jié)點(diǎn)的next后，當(dāng)前節(jié)點(diǎn)就成為該層右側(cè)節(jié)點(diǎn)了。用一個(gè)map來(lái)存儲(chǔ)。
學(xué)習(xí)：同一層次的節(jié)點(diǎn)向右指向next，其實(shí)用BFS的思路最好。不過(guò)看別的代碼，這次BFS沒(méi)有使用queue來(lái)解決，而是巧妙的使用了dummy.next和節(jié)點(diǎn)next，將同一層的節(jié)點(diǎn)連起來(lái)。是學(xué)習(xí)的地方。
代碼

114. Flatten Binary Tree to Linked List

思路：dfs的思路。今天的收獲是：起一個(gè)好的方法名字有利于自己思路形成。以前的代碼都直接將方法命名為dfs，其實(shí)不知道在做什么。今天的方法名flattenNode，是對(duì)node這一個(gè)節(jié)點(diǎn)做展開(kāi)。能夠理清楚一個(gè)節(jié)點(diǎn)做展開(kāi)應(yīng)該做哪些事情，遞歸就好寫(xiě)了。
??????
觀察發(fā)現(xiàn)，例如處理node3，不需要做什么事情。處理node2，能看到node4變成了node3的右子樹(shù)；node3變成了node2的右子樹(shù)。得出如果有左子樹(shù)，那么左子樹(shù)稱為node的右子樹(shù)，原來(lái)node的右子樹(shù)成為現(xiàn)在node右子樹(shù)葉子節(jié)點(diǎn)的右子樹(shù)。把node的左子樹(shù)置為null。
代碼

802. Find Eventual Safe States

思路：開(kāi)始不能明白k的作用，不能明白例題中0,1,3節(jié)點(diǎn)為什么就不可以。
我理解的5,6出度為0，5,6是terminal node，肯定是safe state。節(jié)點(diǎn)2，節(jié)點(diǎn)4可以走到節(jié)點(diǎn)5，所以節(jié)點(diǎn)2，節(jié)點(diǎn)4也屬于safe state。節(jié)點(diǎn)0，節(jié)點(diǎn)1可以走到節(jié)點(diǎn)2，那么節(jié)點(diǎn)0，節(jié)點(diǎn)1也應(yīng)該是safe state。
節(jié)點(diǎn)3能夠走到節(jié)點(diǎn)0，那節(jié)點(diǎn)3也是safe state。所以0,1,2,3,4，5,6應(yīng)該都是safe state。
但題目中有句話是：starting node is eventually safe if and only if we must eventually walk to a terminal node.“ if and only if ”說(shuō)明是可以并且只能走到safe state。
節(jié)點(diǎn)0可以走節(jié)點(diǎn)2，到達(dá)節(jié)點(diǎn)5,；但是同時(shí)節(jié)點(diǎn)0還可以走到節(jié)點(diǎn)1，節(jié)點(diǎn)3,再到節(jié)點(diǎn)0。沒(méi)有任何證據(jù)表名節(jié)點(diǎn)1，或者節(jié)點(diǎn)3不是terminal node，所以節(jié)點(diǎn)0也就不是safe state。也就是不符合 if and only if。這就清楚了，一個(gè)節(jié)點(diǎn)如果它的出度為0或者鏈接的節(jié)點(diǎn)都是safe state的，那它才是safe state。
學(xué)習(xí)：從一個(gè)節(jié)點(diǎn)開(kāi)始深度優(yōu)先進(jìn)行搜索。如果能夠走到終點(diǎn)并且只能走到終點(diǎn)則認(rèn)為無(wú)環(huán)，是一個(gè)safe state。我們將訪問(wèn)節(jié)點(diǎn)的不同狀態(tài)稱為 白-灰-黑：還沒(méi)有開(kāi)始訪問(wèn)節(jié)點(diǎn)是白(0)，開(kāi)始訪問(wèn)一個(gè)節(jié)點(diǎn)是灰(1)，訪問(wèn)一個(gè)節(jié)點(diǎn)結(jié)束是黑(2)。
如果在訪問(wèn)節(jié)點(diǎn)A的過(guò)程中遇到了灰色的節(jié)點(diǎn)B，那么說(shuō)明A在一個(gè)環(huán)內(nèi)。A不是一個(gè)safe state。
如果在訪問(wèn)節(jié)點(diǎn)A的過(guò)程中所有的路徑都能達(dá)到一個(gè)terminal node，沒(méi)有進(jìn)入環(huán)內(nèi)，則A是一個(gè)safe state。
時(shí)間復(fù)雜度O(N+E) N是頂點(diǎn)數(shù)，E是邊數(shù)。
代碼

總結(jié)

以上是生活随笔為你收集整理的Depth-first Search深度优先搜索专题2的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。