Path Sum

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

A leaf is a node with no children.

Class TreeNode:
    val (int)
    left (TreeNode)
    right (TreeNode)

Input Format:

First Parameter - TreeNode root

Second Parameter - number targetSum

Output Format:

Return the number

Example 1:

Input : 
    root = [11 3 6 9 null 9 3 9 7 null null null 8]
    targetSum = 30
Output 
    1
Explanation: 
    The root-to-leaf path with the target sum is shown.

Example 2 :

Input : 
    root = [11 3 9]
    targetSum = 17
Output 
    0
Explanation: 
    There are two root-to-leaf paths in the tree :
    (11 ---> 3) : The sum is 14
    (11 ---> 9) : The sum is 20
    There is no root-to-leaf path with sum = 17.

Constraints :

• The number of nodes in the tree is in the range [1, 5000]
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000
• Expected Time Complexity: O(N)
• Expected Space Complexity: O(N)