Day 16: Path Sum (Tree Depth First Search)

Path Sum

Recommended: Solution

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.

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1]
targetSum = 22
Output: true

# 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

def hasPathSum(root, targetSum):
    if not root:
        return False
    
   
    if not root.left and not root.right:
        return targetSum == root.val
    
    return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum

        

• Time Complexity: O(n), where n is the number of nodes in the tree.
• Space Complexity: O(h), where h is the height of the tree