LeetCode: Path Sum III Solution
If timebox exceeded, read other solutionsApproach
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 = 045 const recursion = (node, prefixSum) => {6 if (!node) return78 prefixSum += node.val910 res +=11 (prefixSum === targetSum) + (prefixSumCount[prefixSum - targetSum] || 0)1213 if (!prefixSumCount[prefixSum]) prefixSumCount[prefixSum] = 01415 prefixSumCount[prefixSum]++16 recursion(node.left, prefixSum)17 recursion(node.right, prefixSum)18 prefixSumCount[prefixSum]--19 }2021 recursion(root, 0)2223 return res24}
References
Similar problems
Path Sum II
Path Sum IV
Longest Univalue Path
Comments
Loading comments...
Tags
leetcode
tree
binary tree
dfs
recursion
Apply and earn a $2,500 bonus once you're hired on your first job!
Clients from the Fortune 500 to Silicon Valley startups
Choose your own rate, get paid on time
From hourly, part-time, to full-time positions
Flexible remote working environment
A lot of open JavaScript jobs!!
Fact corner: Referred talent are 5x more likely to pass the Toptal screening process than the average applicant.
Still hesitate? Read HoningJS author's guide on dealing with Toptal interview process.