Loading problem…
Given the `root` of a binary tree and an integer `targetSum`, return the number of paths where the sum of the values along the path equals `targetSum`. The path does not need to start or end at the root or a leaf, but it must go **downwards** (i.e., traveling only from parent nodes to child nodes).
Example 1
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: Three downward paths add up to 8: 5 → 3, 5 → 2 → 1 and -3 → 11. Paths may start and end anywhere, as long as they go downward.
Example 2
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3
Explanation: Three downward paths add up to 22: 5 → 4 → 11 → 2, 5 → 8 → 4 → 5 and 4 → 11 → 7 (which does not start at the root).
Example 3
Input: root = [1], targetSum = 0
Output: 0
Explanation: The only path is the single node 1, which does not sum to 0.
A downward path summing to target is a contiguous run on some root-to-node chain. Keep the running prefix sum from the root and a count of how many times each prefix value has occurred. A path ending at the current node with sum target exists once for every earlier prefix equal to (current prefix - target).
Run checks all cases above. Submit evaluates all test cases.