```
var pathSum = function(root, sum, presums = { '0': 1 }, prev = 0) {
if (!root) return 0;
let curr = prev + root.val;
presums[curr] = (presums[curr] || 0) + 1;
let res = (presums[curr - sum] || 0) - !sum;
res += pathSum(root.left, sum, presums, curr) + pathSum(root.right, sum, presums, curr);
presums[curr]--;
return res;
};
```

This turns out to be the same as @tankztc's solution here, though I was inspired by backtracking problems since we "backtrack" on the prefix sums.

For a balanced tree we use O(log n) space, otherwise as bad as O(n). Also, I think the "easy" categorization should be changed to "pain in the..." :P.