5.3　路徑和系列問題

力扣（LeetCode）中的路徑和系列問題是典型的可以用DFS來解決的題目。

5.3.1　路徑總和

題目描述（第112題）

給定一個二叉樹和一個目標(biāo)和，判斷該樹中是否存在根節(jié)點到葉子節(jié)點的路徑，這條路徑上所有節(jié)點值相加等于目標(biāo)和。

說明：葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例：給定如下二叉樹，以及目標(biāo)和sum=22。

返回True，因為存在目標(biāo)和為22的根節(jié)點到葉子節(jié)點的路徑5→4→11→2。

解法一　DFS遞歸

思路

題目要求找到一條根節(jié)點到葉子節(jié)點的路徑，并且路徑上所有節(jié)點的值之和等于給定的目標(biāo)值。也就是說，需要搜索這個二叉樹的不同路徑（根節(jié)點到葉子節(jié)點）。如果找到一條符合條件的路徑，則返回True；如果所有的路徑都不符合要求，則返回False。因為題目要求只需要找到一條符合要求的路徑，所以可以使用DFS來處理。

一種直觀的思路是自頂向下，使用前序遍歷+參數(shù)擴展，在向下遞歸的同時更新參數(shù)，當(dāng)?shù)竭_(dá)葉子節(jié)點或空節(jié)點時判斷是否滿足條件。在這里，我們可以將目標(biāo)和sum通過參數(shù)擴展的形式向下傳遞，在葉子節(jié)點上判斷當(dāng)前節(jié)點的val是否等于傳遞下來的參數(shù)sum。這是一種非常常見的DFS解題思路，除了前序遍歷，還有一種常見的二叉樹的深度遍歷法是后序遍歷，即在遞歸函數(shù)返回時對問題進行求解，使用子樹的返回值來計算當(dāng)前節(jié)點的返回值。

通常來講，DFS有遞歸和迭代兩種實現(xiàn)方式。因為樹結(jié)構(gòu)天然具有遞歸的特性（子樹性質(zhì)和整個樹性質(zhì)一致），使用遞歸可以很容易地將整個樹問題轉(zhuǎn)換成子樹問題。當(dāng)我們層層遞歸到最小的子樹時，這個最小子樹的解（也被稱為遞歸出口）往往很容易就能夠得到，再一步步回溯就能得到原問題的解。

小提示：樹的題目，優(yōu)先考慮使用DFS遞歸解決。

當(dāng)我們處理遞歸問題時，如何定義遞歸出口是非常重要的一步（遞歸出口指的是遞歸函數(shù)可以直接處理的最簡單子問題）。對于本題，遞歸出口是當(dāng)當(dāng)前子樹只有一個節(jié)點時（該節(jié)點是整個樹的葉子節(jié)點），需要在遞歸出口判斷當(dāng)前路徑是否符合要求。

一般這種有關(guān)樹的DFS題目，遞歸出口都是葉子節(jié)點或空節(jié)點。

代碼

復(fù)雜度分析

●　時間復(fù)雜度：在最壞情況下，我們會訪問每個節(jié)點各一次，因此時間復(fù)雜度為O(n)，其中n是節(jié)點個數(shù)。

●　空間復(fù)雜度：所需額外的空間和樹的高度呈線性關(guān)系。在最壞情況下，整個樹是非平衡的，每個節(jié)點都只有一個子節(jié)點，完全變?yōu)閱捂湵淼男螒B(tài)，此時樹的高度是n，因此棧的空間開銷是O(n)，但在最好情況下，樹是完全平衡的，高度為logn，在這種情況下空間復(fù)雜度只有O(logn)。

解法二　DFS迭代

思路

對于上面遞歸的寫法，我們可以使用輔助棧將其改寫成迭代的形式。改寫起來也不難，只需要在函數(shù)開始執(zhí)行時壓棧（下圖左邊部分的向下箭頭），函數(shù)返回時出棧(下圖左邊部分的向上箭頭)即可。下圖右邊部分對應(yīng)的是不同階段棧的情況，讀者可以據(jù)此來編寫基于棧的迭代寫法。后面的第113題路徑總和II中的迭代寫法與之類似，讀者只要像這樣畫出圖形，就不難寫出代碼來。

代碼

復(fù)雜度分析

●　時間復(fù)雜度：在最壞情況下，我們會訪問每個節(jié)點各一次，時間復(fù)雜度為O(n)，其中n是節(jié)點個數(shù)，但是使用輔助棧來模擬函數(shù)調(diào)用棧，通常來講速度是更快的，因為函數(shù)調(diào)用棧會有一些其他的時間開銷，也就是說模擬棧會使時間復(fù)雜度的常數(shù)系數(shù)更小。

●　空間復(fù)雜度：空間復(fù)雜度和解法一一致。

5.3.2　路徑總和II

題目描述（第113題）

給定一個二叉樹和一個目標(biāo)和，找到所有從根節(jié)點到葉子節(jié)點路徑總和等于給定目標(biāo)和的路徑。

說明：葉子節(jié)點是指沒有子節(jié)點的節(jié)點。

示例：給定如下二叉樹，以及目標(biāo)和sum=22。

返回[[5,4,11,2]，[5,8,4,5]]。

解法一　DFS遞歸

思路

由題目可以發(fā)現(xiàn)，本題的描述和上一節(jié)幾乎一模一樣。不同的是需要輸出所有符合條件的路徑，而在5.3.1節(jié)中，我們只需要判斷是否存在一條符合條件的路徑即可。

那么該如何在DFS過程中記錄符合條件的路徑呢？

可以在DFS過程中多傳入一個額外的數(shù)組來保存搜索的路徑。回溯時有一個需要注意的細(xì)節(jié)，那就是對路徑數(shù)組進行撤銷的操作，這里可以使用一個小技巧來解決，即在遞歸調(diào)用時使用值傳遞的方式傳遞路徑數(shù)組（而不是直接修改路徑數(shù)組本身）。

另外，我們需要在遞歸出口加上保存符合條件路徑的操作。

和上一節(jié)一樣，本題可以分別使用遞歸和迭代的寫法來解決。

代碼

復(fù)雜度分析

●　時間復(fù)雜度：在最壞情況下，我們會訪問每個節(jié)點各一次，時間復(fù)雜度為O(n)，其中n是節(jié)點個數(shù)。

●　空間復(fù)雜度：所需額外的空間和樹的高度呈線性關(guān)系。在最壞情況下，整個樹是非平衡的，每個節(jié)點都只有一個子節(jié)點，完全變?yōu)閱捂湵淼男螒B(tài)，此時樹的高度是n，因此棧的空間開銷是O(n)，但在最好情況下，樹是完全平衡的，高度為logn，在這種情況下空間復(fù)雜度只有O(logn)。

解法二　DFS迭代

代碼

復(fù)雜度分析

●　時間復(fù)雜度：在最壞情況下，會訪問每個節(jié)點各一次，時間復(fù)雜度為O(n)，其中n是節(jié)點個數(shù)。

●　空間復(fù)雜度：所需額外的空間和樹的高度呈線性關(guān)系。在最壞情況下，整個樹是非平衡的，每個節(jié)點都只有一個子節(jié)點，完全變?yōu)閱捂湵淼男螒B(tài)，此時樹的高度是n，因此棧的空間開銷是O(n)，但在最好情況下，樹是完全平衡的，高度為logn，在這種情況下空間復(fù)雜度只有O(logn)。

5.3.3　二叉樹中的最大路徑和

題目描述（第124題）

給定一個非空二叉樹，返回其最大路徑和。

本題中，路徑被定義為一條從樹中任意節(jié)點出發(fā)并達(dá)到任意節(jié)點的序列。該路徑至少包含一個節(jié)點，且不一定經(jīng)過根節(jié)點。

示例

輸入：[1,2,3]

輸出：6

思路

我們知道，樹本身是圖的一種特例，找樹中任意起點的最大路徑和其實就是找圖中的最大權(quán)值和。

我們先思考一種簡單的情況——只有3個節(jié)點的子樹。

它包含的路徑和總共有6種。

●　b。

●　c。

●　a。

●　a+b。

●　a+c。

●　b+a+c。

b和c分別是單節(jié)點子樹的最大值（也就是該節(jié)點本身）。

假設(shè)上面這個子樹是整個樹的一部分，那么對于獲取最終答案而言，該子樹可能的貢獻(xiàn)有如下3種情況。

●　整個樹的最大路徑和就在這個子樹當(dāng)中，不再經(jīng)過這個子樹外的其他節(jié)點，則最終結(jié)果是。

?　取a表示b和c都無法給最大路徑和做貢獻(xiàn)，也就是都小于0。

?　取b或c與取a類似。

?　取a+b+c表示b和c都給最大路徑和做貢獻(xiàn)，也就是都大于0。

?　取a+b表示c無法給最大路徑和做貢獻(xiàn)，也就是小于0。

?　取a+c與a+b類似。

●　最大路徑和包含節(jié)點a，并且通過a擴展到子樹外的其他節(jié)點。這里 表示最大路徑和中由節(jié)點a往外延伸的剩余部分路徑和，最終結(jié)果是。

●　不包含子樹a。

如果把節(jié)點b和c抽象成任意一個子樹的左/右子樹，我們便可以將子樹a的情況擴展到整個樹，實現(xiàn)從特例到全局的抽象。遇到這類可以用同種邏輯處理問題及其子問題的情況，使用遞歸思想是一個不錯的思路。

設(shè)定一個全局變量存儲最大路徑和，不斷遞歸搜索每個子樹更新該變量。

●　首先搜索的是最左邊的最小子樹，不斷回溯到更大一點的子樹，直到root節(jié)點的整個左子樹被搜索完成。

●　然后對root節(jié)點的右子樹做同樣的操作。

●　最后再判斷包含root節(jié)點的情況。

由前面的分析可以看出，對于這道題來說，對于樹中的任意一個節(jié)點，如果知道它子節(jié)點的答案，就能計算出當(dāng)前節(jié)點的答案，因此我們使用自底向上的后序遍歷來完成。

詳細(xì)的代碼非常簡潔、易懂，如下所示。

復(fù)雜度分析

●　時間復(fù)雜度：因為尋找的是最大路徑和，所以我們會訪問每個節(jié)點各一次，因此時間復(fù)雜度為O(n)，其中n是節(jié)點個數(shù)。

●　空間復(fù)雜度：所需額外的空間和樹的高度呈線性關(guān)系。在最壞情況下，整個樹是非平衡的，每個節(jié)點都只有一個子節(jié)點，完全變?yōu)閱捂湵淼男螒B(tài)，此時樹的高度是n，因此棧的空間開銷是O(n)，但在最好情況下，樹是完全平衡的，高度為logn，在這種情況下空間復(fù)雜度只有O(logn)。