Leetcode•Aug 30, 2025
Path Sum III
Hazrat Ali
Leetcode
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: The paths that sum to 8 are shown.
Example 2:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output: 3
Solution
/**
*
* @param {TreeNode} root
* @param {number} sum
* @return {number}
*/
const pathSum = (root, sum) => {
const helper = (root, current, sum, prefixSum) => {
if (!root) {
return 0;
}
current += root.val;
var count = ~~prefixSum[current - sum];
prefixSum[current] = ~~prefixSum[current] + 1;
count += helper(root.left, current, sum, prefixSum) + helper(root.right, current, sum, prefixSum);
prefixSum[current]--;
return count;
};
return helper(root, 0, sum, { 0: 1 });
};