710 - Python LeetCode

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

題目出處

112. Path Sum

難度

easy

個人範例程式碼

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:

        return self.dfs(root, targetSum, [])

    def dfs(self, root, target, path):
        # Null
        if not root:
            return False

        path.append(root.val)
        # leaf
        if not root.left and not root.right:
            if sum(path) == target:
                path.pop()
                return True

        # not leaf
        ans = self.dfs(root.left, target, path) or self.dfs(root.right, target, path) # need pop path before return
        path.pop()

        return ans

算法說明

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

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

input handling

如果沒有正確結果，回傳 False

Boundary conditions

end of recursion

判斷 Null 或是 Leaf

  • Null

False

# Null
if not root:
    return False
  • Leaf

判斷是否總和正確，如果是回傳 True

# leaf
if not root.left and not root.right:
    if sum(path) == target:
        path.pop()
        return True

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
ans = self.dfs(root.left, target, path) or self.dfs(root.right, target, path) # need pop path before return

Reference