5.1　深度優(yōu)先遍歷

使用DFS進(jìn)行解題的大概思路是定義起始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)，從起點(diǎn)開(kāi)始不斷深入其他節(jié)點(diǎn)，在搜索的過(guò)程中判斷是否滿足特定條件，偽代碼如下。

上面的visited是為了防止由于環(huán)的存在而造成死循環(huán)的，不管是BFS還是DFS，如果是在二維矩陣或圖上進(jìn)行搜索，通常都需要visited來(lái)記錄節(jié)點(diǎn)訪問(wèn)狀態(tài)。也可以使用原地標(biāo)記，比如后面要講的島嶼問(wèn)題就使用了這個(gè)技巧。

如果在樹(shù)的題目中使用DFS，由于樹(shù)是不存在環(huán)的，因此有關(guān)樹(shù)的題目大多數(shù)不需要visited，但是如果對(duì)樹(shù)的結(jié)構(gòu)做了修改，使之出現(xiàn)了環(huán)，那就仍然需要 visited。例如第138題復(fù)制帶隨機(jī)指針的鏈表，這道題需要記錄已經(jīng)復(fù)制的節(jié)點(diǎn)。因此一個(gè)樹(shù)的DFS代碼在更多情況下應(yīng)該是下面這樣的。

而幾乎所有有關(guān)樹(shù)的題目都是二叉樹(shù)，因此下面這樣的代碼更常見(jiàn)。

由于二叉樹(shù)的簡(jiǎn)潔性，建議讀者從二叉樹(shù)開(kāi)始練習(xí)DFS和BFS，然后將這些思想和技巧推廣到其他更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，例如圖。

對(duì)于二叉樹(shù)的題目，除了遞歸出口的條件，還會(huì)寫(xiě)一些其他的邏輯，這些邏輯由于位置的不同，產(chǎn)生的效果也截然不同。根據(jù)DFS邏輯位置的不同，我們將其分為三種類型，一種是自頂向下（前序遍歷）的，一種是自底向上（后序遍歷）的，最后一種是中序遍歷。

前序遍歷就是在每個(gè)遞歸層級(jí)上首先訪問(wèn)節(jié)點(diǎn)來(lái)計(jì)算一些值，并在遞歸調(diào)用函數(shù)時(shí)將這些值傳遞到子節(jié)點(diǎn)，一般是通過(guò)參數(shù)傳到子樹(shù)中。

偽代碼如下。

后序遍歷是另一種常見(jiàn)的遞歸方法，首先對(duì)所有子節(jié)點(diǎn)遞歸地調(diào)用函數(shù)，然后根據(jù)返回值和根節(jié)點(diǎn)本身的值得到答案。

作者的經(jīng)驗(yàn)總結(jié)如下。

●　大多數(shù)有關(guān)樹(shù)的題目使用后序遍歷會(huì)比較簡(jiǎn)單，并且大多需要依賴左/右子樹(shù)的返回值。例如第1448題統(tǒng)計(jì)二叉樹(shù)中好節(jié)點(diǎn)的數(shù)目。

●　也有一部分有關(guān)樹(shù)的題目需要前序遍歷，而前序遍歷通常要結(jié)合參數(shù)擴(kuò)展技巧。例如第1022題從根到葉的二進(jìn)制數(shù)之和。

●　如果能使用參數(shù)和節(jié)點(diǎn)本身的值來(lái)決定應(yīng)該傳遞給它的子節(jié)點(diǎn)的參數(shù)，那么就用前序遍歷。

●　對(duì)于樹(shù)中的任意一個(gè)節(jié)點(diǎn)，如果知道它子節(jié)點(diǎn)的答案，就能計(jì)算出當(dāng)前節(jié)點(diǎn)的答案，那么就用后序遍歷。

●　如果遇到二叉搜索樹(shù)，則考慮使用中序遍歷。

讀者熟悉了二叉樹(shù)的DFS技巧之后，再嘗試將其推廣到其他數(shù)據(jù)結(jié)構(gòu)會(huì)輕松很多。