# **Leetcode筆記(Path Sum)**

:::info
:information_source: 題目 : Path Sum, 類型 : binary tree , 等級 : easy
日期 : 2023/10/18，2023/12/10，2024/02/20，2025/02/15
:::

### 嘗試
2023/12/10

"""
if not root:
    return False
return dfs(root, 0)
def dfs():
    if they are leaf:
        compare temp = targetSum
        if temp == targetSum:
            return True
    
    return dfs(node.left, temp + node.val) or
    dfs(node.right, temp + node.val)

"""
class Solution(object):
    def hasPathSum(self, root, targetSum):
        if not root:
            return False
        
        def dfs(node, temp):
            if not node:
                return 
            
            temp += node.val

            if not node.left and not node.right:
                if temp == targetSum:
                    return True
                else:
                    return 
            
            return dfs(node.left, temp) or dfs(node.right, temp)
        
        return dfs(root, 0)
        

2024/02/20

class Solution:
    def __init__(self):
        self.i = False
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return self.i
        self.traverse(root, 0, targetSum)
        return self.i

    def traverse(self, node, total, targetSum):
        if not node:
            if total == targetSum:
                self.i = True
            return
        
        total += node.val
        self.traverse(node.left, total, targetSum)
        self.traverse(node.right, total, targetSum)

2025/02/15

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        return self.traverse(root, targetSum)

    def traverse(self, node, total):

        total -= node.val

        if total == 0 and not node.left and not node.right:
            return True
        
        if node.left and self.traverse(node.left, total):
            return True
        if node.right and self.traverse(node.right, total):
            return True
        
        return False

---
### **優化**
當沒有左右小孩的時候，就去檢查加法是否正確
非嚴格正確，如果有一個正確的，那就會傳True

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False

        def dfs(node, total):
            if not node:
                return False

            total += node.val
            if not node.right and not node.left:
                return total == targetSum
            
            return (dfs(node.right, total) or dfs(node.left, total))

        return dfs(root, 0)

---

**思路**

**講解連結**
https://www.youtube.com/watch?v=LSKQyOz_P8I
Provided by. NeetCode