LeetCode: Path Sum III Solution

Approach

Prefix sum is equivalent to accumulated sum

Final result is the sum of

• prefixSum === targetSum: the current path sum is equal to target sum
• prefixSumCount[prefixSum - targetSum]: number of sub-paths, each of whose is equal to target sum

Implementation

1var pathSum = function (root, targetSum) {
2  const prefixSumCount = {}
3  let res = 0
4
5  const recursion = (node, prefixSum) => {
6    if (!node) return
7
8    prefixSum += node.val
9
10    res +=
11      (prefixSum === targetSum) + (prefixSumCount[prefixSum - targetSum] || 0)
12
13    if (!prefixSumCount[prefixSum]) prefixSumCount[prefixSum] = 0
14
15    prefixSumCount[prefixSum]++
16    recursion(node.left, prefixSum)
17    recursion(node.right, prefixSum)
18    prefixSumCount[prefixSum]--
19  }
20
21  recursion(root, 0)
22
23  return res
24}

References

Original problem

Similar problems

Path Sum

Path Sum II

Path Sum IV

Longest Univalue Path