NO IMAGE

樹的求和屬於樹的題目中比較常見的,因為可以有幾種變體,靈活度比較高,也可以考察到對於樹的資料結構和遞迴的理解。一般來說這些題目就不用考慮非遞迴的解法了(雖然其實道理是跟LeetCode總結 — 樹的遍歷篇一樣的,只要掌握了應該沒問題哈)。 LeetCode中關於樹的求和有以下題目:
Path Sum
Path Sum 2
Sum Root to Leaf Numbers
Binary Tree Maximum Path Sum

我們先來看看最常見的題目Path Sum。這道題是判斷是否存在從根到葉子的路徑和跟給定sum相同。樹的題目基本都是用遞迴來解決,主要考慮兩個問題:
1)如何把問題分治成子問題給左子樹和右子樹。這裡就是看看左子樹和右子樹有沒有存在和是sum減去當前結點值得路徑,只要有一個存在,那麼當前結點就存在路徑。
2)考慮結束條件是什麼。這裡的結束條件一個是如果當前節點是空的,則返回false。另一個如果是葉子,那麼如果剩餘的sum等於當前葉子的值,則找到滿足條件的路徑,返回true。
想清楚上面兩個問題,那麼實現起來就是一次樹的遍歷,按照剛才的分析用引數或者返回值傳遞需要維護的值,然後按照遞迴條件和結束條件進行返回即可。演算法的時間複雜度是一次遍歷O(n),空間複雜度是棧的大小O(logn)。
對於Path Sum II,其實思路和Path Sum是完全一樣的,只是需要輸出所有路徑,所以需要資料結構來維護路徑,新增兩個引數,一個用來維護走到當前結點的路徑,一個用來儲存滿足條件的所有路徑,思路上遞迴條件和結束條件是完全一致的,空間上這裡會依賴於結果的數量了。
Sum Root to Leaf Numbers這道題多了兩個變化,一個是每一個結點相當於位上的值,而不是本身有權重,不過其實沒有太大變化,每一層乘以10加上自己的值就可以了。另一個變化就是要把所有路徑累加起來,這個其實就是遞迴條件要進行調整,Path Sum中是判斷左右子樹有一個找到滿足要求的路徑即可,而這裡則是把左右子樹的結果相加返回作為當前節點的累加結果即可。
變化比較大而且有點難度的是Binary Tree Maximum Path Sum,這道題目的路徑要求不再是從根到葉子的路徑,這個題目是把樹完全看成一個無向圖,然後尋找其中的路徑。想起來就覺得比上面那種麻煩許多,不過仔細考慮會發現還是有章可循的,找到一個根節點最大路徑,無非就是找到左子樹最大路徑,加上自己的值,再加上右子樹的最大路徑(這裡左右子樹的路徑有可能不取,如果小於0的話)。我們要做的事情就是對於每個結點都做一次上面說的這個累加。而左子樹最大路徑和右子樹最大路徑跟Path Sum II思路是比較類似的,雖然不一定要到葉子節點,不過標準也很簡單,有大於0的就取,如果走下去路徑和小於0那麼就不取。從分治的角度來看,左右子樹的最大路徑就是取自己的值加上Max(0,左子樹最大路徑,右子樹最大路徑)。這麼一想也就不用考慮那麼多細節了。而通過當前節點的最長路徑則是自己的值 Max(0,左子樹最大路徑) Max(0,右子樹最大路徑)。所以整個演算法就是維護這兩個量,一個是自己加上左或者右子樹最大路徑作為它的父節點考慮的中間量,另一個就是自己加上左再加上右作為自己最大路徑。具體的實現可以參見Binary Tree Maximum Path Sum
這篇總結主要講了LeetCode中關於樹的求和的題目。總體來說,求和路徑有以下三種:(1)根到葉子結點的路徑;(2)父結點沿著子結點往下的路徑;(3)任意結點到任意結點(也就是看成無向圖)。這幾種路徑方式在面試中經常靈活變化,不同的路徑方式處理題目的方法也會略有不同,不過最複雜也就是Binary Tree Maximum Path Sum這種路徑方式,只要考慮清楚仍然是一次遞迴遍歷的問題哈。