從LeetCode學演算法 - 104 Tree (17) / DFS (14) / Backtracking (6)

0113. Path Sum II (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

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

Return:

1
2
3
4
[
   [5,4,11,2],
   [5,8,4,5]
]

分析/解題
給定一個二元樹以及目標的和(sum)，找出所有根節點到葉的路徑，這些路徑各自的和要等於給定的和。

這一題是一整組Path Sum系列題的第二題。
由於要找出路徑，所以我們需要一組記錄當前路徑current的位置的list。
同時，要能夠判定是否要確認這條路徑OK的狀態，
只取決於現在是否走到葉節點(因為題目要求)；
並且走到葉節點時，左右也都沒有節點了，就無法往下走。

我們可以用一個result的list記錄最終處理完的結果，
接著使用DFS 的方式往下找。

那麼自然我們每走過一個節點，
就要將sum減去現在root的値，同時記錄到current上。

接下來要往下走還是檢查呢？
當然就是看左右節點是否為NIL且sum和root的値是否相等啦！
如果是的話，可以將result加上走到現在的路徑；
如果不是的話，則以DFS往左和往右走(不要忘記去檢查NIL的狀況)。
這整段走完要回到上一層的時候，表示已經處理完了，
不要忘記我們先前將這層root的値放進了current裡面，
所以我們應該要將其移除。(** Backtracking**的部分)

依此，寫成程式碼如下：

Java

Java的部分我們可以使用同名但不同參數長度的函式，
直接利用開頭檢查root，
來順便處理後續帶入root.left/root.right所需要的檢查。
Backtracking的部分，
currentResult先加上root.val後，後續再進行remove即可；
而留意由於我們不斷地在變換currentResult，
不要忘記要將其複製一份以加到result裡面，而非直接用加的。
(使用new LinkedList(currentResult) )

Python

同理，Python的部分一樣需要複製，
我們可以寫成curr[:]以複製一份用來讓res進行附加。

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

「時間/空間複雜度？」
(O(N)/O(logN)，因為整棵樹要遍歷過一遍，
然後平均而言，樹的深度會到O(logN)，
所以空間複雜度所以空間複雜度，這個部分不包含result的占用空間)

相似及延伸

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

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

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