Path Sum III

Given the root of a binary tree and an integer targetSum, return the number of paths that sum to targetSum. The path must go downward and may start and end at any node. Pattern focus: Global Variable for Cross-Root Paths. Use prefix-sum counting while traversing the tree.

Input Format

root = binary tree root, targetSum = required path sum

Output Format

number of downward paths that sum to 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 = [10,5,-3,3,2,null,11,3,-2,null,1]
targetSum = 8

Output:

3

Explanation:

There are 3 downward paths whose sum is 8.

Example 2:

Input:

root = [1,-1,0]
targetSum = 0

Output:

2

Explanation:

The paths [1,-1] and [0] both sum to 0.

Loading...
Path Sum III - Binary Tree DSA Problem