題目出處

難度

medium

個人範例程式碼

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        ans = []
        self.dfs(root, targetSum, [], ans)
        return ans

    def dfs(self, root, target, path, ans):
        # None
        if not root:
            return 

        path.append(root.val)
        # Leaf
        if not root.left and not root.right:
            if sum(path) == target:
                ans.append(path[:]) # copy a new one
                path.pop()
                return

        # not leaf
        self.dfs(root.left, target, path, ans)
        self.dfs(root.right, target, path, ans)
        path.pop()

        return

算法說明

此題的前一個題目，不同處在於需要多求出完整路徑，可參考：

https://wongwongnotes-github-io.pages.dev/python/leetcode-python-112/

基礎的 DFS 用來 traverse Tree 裡面的內容，並沿路計算總和。

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

input handling

如果沒有正確結果，回傳 []

Boundary conditions

end of recursion

判斷 Null 或是 Leaf

Null

False

if not root:
    return

Leaf

判斷是否總和正確，如果是則加入目前的 path

注意：因為 list 在 python function 中，pass by assignment 可以變更 mutable object
因此我們複製時要複製「ans.append(path[:])」，等於創造出一個新的物件，
不然最後的結果會隨著 path 改變而跟著變動。

# Leaf
if not root.left and not root.right:
    if sum(path) == target:
        ans.append(path[:]) # copy a new one
        path.pop()
        return

define of recursion

增加路過的路徑。

path.append(root.val)

重要：這邊務必注意，因為 list 在 python function 中，pass by assignment 可以變更 mutable object，所以勢必要注意對應的 pop() 位置在哪。

path.pop()

split of recursion

拆成兩路，同樣的也如同我們上面說要注意的點。
我們先把結果拿回來，再把 path 的內容先 pop 出來後，再把 ans 回傳。

# not leaf
self.dfs(root.left, target, path, ans)
self.dfs(root.right, target, path, ans)
path.pop()

【Leetcode】python - [113] Path Sum II 個人解法筆記