Path Sum III Medium 0 attempts
LeetCode ↗

Path Sum III

Medium TreeBinary TreeDFS LeetCode

You're given the root of a binary tree and a target sum. Count how many downward paths add up exactly to that target — a path follows parent-to-child links but doesn't have to begin at the root or finish at a leaf.

Input Format
Implement pathSum(root, targetSum). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
root = [1]
targetSum = 1
Output
1
Constraints
  • 0 <= number of nodes <= 1000
  • -10^9 <= Node.val <= 10^9
  • -1000 <= targetSum <= 1000
Test Cases (2)
Case 1
Args: [[10,5,-3,3,2,null,11,3,-2,null,1],8] Expected: 3
Case 2
Args: [[1],1] Expected: 1
Topics
TreeBinary TreeDFS

Prefix Sum DFS

javascript
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