LC 0112 [E] Path Sum - ALawliet/algorithms GitHub Wiki

# 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: TreeNode, targetSum: int) -> bool:
        self.has_sum = False

        def dfs(node, slatesum):
            if not node.left and not node.right: # leaf
                if slatesum + node.val == targetSum:
                    self.has_sum = True
                    return

            if node.left:
                dfs(node.left, slatesum + node.val)

            if node.right:
                dfs(node.right, slatesum + node.val)
                
        if root is None: return False
        dfs(root, 0)
        return self.has_sum

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right and root.val == sum:
            return True
        return self.hasPathSum(root.left, sum - root.val) or self.hasPathSum(root.right, sum - root.val)