---
# System prepended metadata

title: '**Leetcode筆記(Path Sum)**'
tags: [easy, binary tree, microsoft, leetcode]

---

# **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
```python
"""
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
```python
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
```python
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
```python
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
