mediumTreesPure DSA~30 min
Count Downward Paths Summing to a Target
In a tree of signed metric deltas, count how many downward paths (parent toward child, not necessarily starting at the root) sum to a target value.
Problem
Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of node values equals targetSum. Paths must go downward (parent to child) but need not start at the root or end at a leaf.
Input
A binary tree root and an integer targetSum.
Output
An integer: the count of qualifying downward paths.
Constraints
- 0 <= number of nodes <= 1000
- -10^9 <= node values, targetSum <= 10^9
- Path sums fit in 64-bit integers.
Examples
Example 1
Input
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output
3
Three downward paths sum to 8.
Example 2
Input
root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output
3
Three distinct downward paths reach 22.