1 題目描述



給定一個sum，判斷是否存在一條從根節點到葉子節點的路徑，使得路徑上所有節點的值的和等於sum。

2 解法

這題不難，我們只要在往下遍歷的時候，每次減去當前節點的值，然後判斷是否為0即可。這題可以用DFS的方式解。

如果Root是空的回傳False，否則剪掉當前的節點

1
2
3
4
if not root:
    return False
else:
    targetSum -= root.val

如果發現root.left且root.right都是None代表觸底，檢查targetSum是否為None

1
2
if not root.left and not root.right:
    return targetSum == 0

只要root還不是最底層的leaf，就繼續往下，如果左右子樹其中一個有True就回傳True

1
return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

完整的程式碼

1
2
3
4
5
6
7
8
9
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        targetSum -= root.val
        if not root.left and not root.right:
            return targetSum == 0

        return self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)

3 結論

這題是一個簡單的DFS，只要在遍歷的時候，每次減去當前節點的值，然後判斷是否為0即可。這題可以用DFS的方式解。大概5-10分鐘寫完。