Description
Given a binary tree and a targetSum, return the number of paths where the sum of values along the path equals targetSum. Path can start anywhere.
Examples
Input:
root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8Output:
3Explanation:
Three paths sum to 8.
Input:
root = [1,2,3,4,5], targetSum = 3Output:
2Explanation:
Two paths sum to 3: [3] (the right child of root) and [1,2] (root to left child).
Input:
root = [-2,-1,3], targetSum = -3Output:
1Explanation:
One path sums to -3: [-2,-1] (root to left child). This demonstrates the algorithm works with negative numbers.
Constraints
- •
0 ≤ nodes ≤ 1000