112. Path Sum

• categories: Code, Interview Question, leetcode, Easy
• source: https://leetcode.com/problems/path-sum/description
• topics: Tree

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.

Depth-first search

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        
        targetSum -= root.val
 
        if not root.left and not root.right and targetSum == 0:
            return True 
 
        return (self.hasPathSum(root.left, targetSum) or
                self.hasPathSum(root.right, targetSum))