Path Sum

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. Pattern focus: Root To Leaf Paths. Track the current sum along each path and check leaf completion.

Input Format

root = binary tree root, targetSum = required sum

Output Format

true if there exists a root-to-leaf path with sum targetSum

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

true

Explanation:

The path 5 -> 4 -> 11 -> 2 sums to 22.

Example 2:

Input:

root = [1,2,3]
targetSum = 5

Output:

false

Explanation:

No root-to-leaf path sums to 5.

Loading...
Path Sum - Binary Tree DSA Problem