112. Path Sum

Path Sum - LeetCodeLeetCode

def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
    def path_sum(node,s):
        if not node:
            return False
        s += node.val
        # 代表走到終點
        if not node.left and not node.right and s == targetSum:
            return True
        
        return path_sum(node.left,s) or path_sum(node.right,s)
        
    return path_sum(root,0)

題目重點：

• 終止條件：如果當前節點沒有左右子節點，就檢查當前路徑和是否等於 targetSum。如果相等，則返回 True。

• 遞歸處理：如果還未到達葉子節點，就遞歸地向左子樹和右子樹進行搜索，並將當前累加的路徑和傳入到下一層。

其他

or 的特性：

• or 的特性是：如果兩邊的結果都是 False，則返回 False；

• 只要有一邊的結果是 True，整個表達式就會返回 True。

• 這意味著，左右子樹只要有一條路徑滿足條件，就能立即返回 True，否則返回 False。

return path_sum(node.left,s) or path_sum(node.right,s)