总结

该网页是一篇关于LeetCode算法题解的文章，题目为Path Sum II，介绍了如何找到所有根节点到叶子节点的路径，使得路径上节点值之和等于给定的目标值。

摘要

该网页是一篇关于LeetCode算法题解的文章，题目为Path Sum II。题目要求给定一棵二叉树和一个目标值，找到所有根节点到叶子节点的路径，使得路径上节点值之和等于给定的目标值。作者首先介绍了题目的要求和示例，然后分析了题目的解题思路，并提供了Java和Python的解题代码。最后，作者讨论了该题目在面试中的可能性和相似问题。

观点

该题目是一整组Path Sum系列题的第二题。
要找到所有根节点到叶子节点的路径，需要使用DFS（深度优先搜索）的方法。
要判断是否要确认这条路径是否满足条件，需要看当前节点是否是叶子节点，即左右节点都为空。
要记录当前路径，需要使用一个list来记录。
要处理当前节点，需要将目标值减去当前节点的值，并将当前节点的值加入到list中。
要继续搜索下一个节点，需要判断当前节点的左右节点是否为空，如果不为空，则继续搜索左右节点。
在面试中，该题目可能会问到时间和空间复杂度，时间复杂度为O(N)，空间复杂度为O(logN)。

從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學演算法｜面試篇」課程的免費兌換券進行贈送！

請幫我隨手點開下面的SHOW EMBED並按5個like～喜歡的話也可以幫我拍拍手～ (按讚不用錢，感謝支持寫作~)

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,

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

Return:

[
   [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

如果你／妳覺得這篇文章不錯，請拍手並給5個Like。(點開SHOW EMBED!)
也請記得「Follow」我，隨時收看最新的文章。