Path Sum

Problem Statement: 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.

Example 1:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Constraints:

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

Source: https://leetcode.com/problems/path-sum/

Asked in: Facebook Amazon ,Apple

Leetcode Difficulty: Easy

Code:

    def check(self, root, targetSum, pathSum=0):
        if not root: return
            
        pathSum+=root.val
        
        if pathSum==targetSum and root.left==None and root.right==None: return True
        return self.check(root.left, targetSum, pathSum) or self.check(root.right, targetSum, pathSum)
    
    def haspathsum(self, root, targetSum):
        """
        root: TreeNode
        targetSum: int
        return: bool
        """
        return self.check(root, targetSum)

Thought Process / Explanation:

Keep summing the root values in paths we iterate and compare pathSum with targetSum if the root at that point is a leaf node. Do this for left and right parts of the tree.

Thank You!