0437. Path Sum III (Medium)

寫在前面

容筆者工商一下， 「從Leetcode學演算法｜進階篇」及 加贈的**「從Leetcode學演算法｜面試篇」已經全數上傳完囉！**

目前只剩下給讀者的進階篇+面試篇(3150) 和全套同捆優惠(3990) 了QQ
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」：
https://bit.ly/leetcodeadv
「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/leetcodeall

內容介紹：
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

Question

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

1

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

1
2
3
4
5
6
7

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

1

Return 3. The paths that sum to 8 are:

1
2
3

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

分析/解題

給定一個二元樹，當中每個節點均含一個整數，
找出所有可以加總等於目標總和的路徑數量。
一個路徑不需要從根節點開始，也不必一定要到葉節點結束，
但是路徑只能往下走(也就是說只能從父節點往子節點走)；
另外，這棵樹最多只會有1000個節點，
且其值均在-1000000~1000000之間。

這一題是一整組Path Sum系列題的第三題。
由於題目提示節點數不會超過1000個，
所以基本是無法超過各程式的Call Stack限制，可以放心使用遞迴。

那麼，我們看看另一個重點：
路徑只能往下走，會有什麼特點呢？
舉例來說，以上面的二元樹，當我們走到某個節點2時，
所有終點是2的路徑有以下三種：
10 -> 5 -> 2 
5 -> 2
2
再往下走到1的時候，路徑有以下四種：
10 -> 5 -> 2 -> 1
5 -> 2 -> 1
2 -> 1
1

我們可以發現，走到1的路徑和到底有沒有符合target的解這件事情，
可以透過兩點知道：

1. 從root起算走到現在這個節點的總和是否和target相等
2. 從root起算走到現在這個節點的總和-target是否在過往出現過

第2點比較抽象，我們稍微舉一下簡單的例子：
假設我們要找的目標是8的話，
那麼直接看我們當然知道是5->2->1，
但如果不能回頭重算的話，要怎麼辦呢？
我們可以得到5->2->1的路徑，
其實相當於從根節點10走到1的路徑和，減去節點10。

換句話說，如果我們每走到一個節點，都將路徑和記錄下來，
那麼我們就可以用前面過往的路徑和，
來表達出所有達到現在這個節點的路徑和。

例如：
1其實等於10 -> 5 -> 2 -> 1 去掉** 10 -> 5 -> 2
2** -> 1等於** 10 -> 5 -> 2** -> 1去掉** 10 -> 5
5 -> 2** -> 1等於** 10 -> 5 -> 2** -> 1去掉** 10**

這樣足夠清楚了嗎XD？
因此，我們要做的事情有：
0. 建一個dictionary或hashmap，
當中key/value分別代表路徑和/路徑和出現的次數。
同時，將(0, 1)置入字典當中。(這裡稱之為preSum)
(方便我們在剛好等於根節點到當前節點總長時計算)

1. 呼叫遞迴DFS函式並回傳其結果。

2. 在DFS函式中，遍歷整棵二元樹：
   2.0. 檢查節點是否存在，不存在則回傳0
   2.1. 將當前的節點值加上根節點的値，做為現在的總和(currSum)
   2.2. 初始化res，其值為currSum-target在preSum中出現的次數
   2.3. 分別向左右節點遞迴呼叫DFS函式，將得到的結果加到res
   2.4. 由於這條路徑只能一路向下，
   所以要回到上一層前，
   需將剛剛加過的1次記錄從preSum中扣掉(backtracking)。
   2.5. 回傳res

依此，寫成程式碼如下：

Java

Java的部分preSum使用HashMap，留意先進行一次put，
再放入helper函式中做DFS；
helper函式中的部分，由於HashMap本身找不存在的值會出錯，
別忘了使用getOrDefault來給定預設值(當然，你要用containsKey也行)。
在遞迴取得左右兩邊節點的符合路徑數加總後，
別忘記回傳前要將加上去的刪掉，才符合回溯法的要件。

Python

Python的部分大同小異，
不同的是我們可以用defaultdict來將預設值當作0，
從Python的寫法中應該可以更清晰看見回溯法的樣貌。
(先加1後減1)
這邊的helper直接寫成子函式，
所以我們就不需使用self.xxx的形式來呼叫了。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N*樹深)，每個節點均需要經過一次，
每個節點最多可以成立d個preSum值，
d為樹的深度，以平衡樹來說則是log(N))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

另外，「從Leetcode學演算法｜基礎篇」 已經回原價囉，
先前的優惠碼會失效，但這邊仍然為讀者保留了300塊的折抵，
雖然整捆一起買總體比較划算 (差290而已就有整組了阿XD)，
如果你還是想先試試基礎課的話，
300元折抵的連結 在這邊：
https://bit.ly/1desolve