Path Sum III Medium 0 attempts
LeetCode ↗

Path Sum III

Medium TreeBinary TreeDFS LeetCode

Given a binary tree, find the number of paths where values sum to a given target. Path doesn't need to start at root or end at leaf.

Example: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 → Output: 3

Sample Input
—
Sample Output
—
Constraints
  • 0 <= number of nodes <= 1000
  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000
Topics
TreeBinary TreeDFS

Prefix Sum DFS

function pathSum(root, targetSum) {
  let count = 0;
  const prefixSums = new Map([[0, 1]]);
  function dfs(node, sum) {
    if (!node) return;
    sum += node.val;
    count += prefixSums.get(sum - targetSum) || 0;
    prefixSums.set(sum, (prefixSums.get(sum) || 0) + 1);
    dfs(node.left, sum); dfs(node.right, sum);
    prefixSums.set(sum, prefixSums.get(sum) - 1);
  }
  dfs(root, 0);
  return count;
}

Time: O(n) | Space: O(n)

Saved in this browser only. Private to you.

JavaScript