LeetCode: Path Sum III Solution

If timebox exceeded, read other solutions

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

Comments

Loading comments...

Tags

leetcode

tree

binary tree

dfs

recursion

Next Post

LeetCode: Path Sum

Keep subtracting

Previous Post

HoningJS

Search Posts