[LeetCode] 112 | Path Sum | Python

---

문제 링크: https://leetcode.com/problems/path-sum/

---

문제

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

---

조건

• The number of nodes in the tree is in the range [0, 5000].
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

---

내 풀이

root부터 leaf까지의 수를 다 합한 뒤 그것이 targetSum과 같으면 True를 리턴한다.

모든 leaf까지의 경로를 다 해봤는데 targetSum과 같은 것이 없다면 False를 리턴한다.

---

코드

# 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:
        def pathSum(root, cur_sum):
            if not root:
                return False
            
            cur_sum += root.val
            if cur_sum == targetSum and not root.left and not root.right:
                return True
            
            return pathSum(root.left, cur_sum) or pathSum(root.right, cur_sum)
        
        return pathSum(root, 0)