Concise JavaScript O(n) solution using map
\nvar pathSum = function(root, sum, presums = { '0': 1 }, prev = 0) {\n    if (!root) return 0;\n    let curr = prev + root.val;\n    presums[curr] = (presums[c
```\nvar pathSum = function(root, sum, presums = { '0': 1 }, prev = 0) {\n    if (!root) return 0;\n    let curr = prev + root.val;\n    presums[curr] = (presums[curr] || 0) + 1;\n    let res = (presums[curr - sum] || 0) - !sum;\n    res += pathSum(root.left, sum, presums, curr) + pathSum(root.right, sum, presums, curr);\n    presums[curr]--;\n    return res;\n};\n```\nThis turns out to be the same as @tankztc's solution [here](https://discuss.leetcode.com/topic/64526/17-ms-o-n-java-prefix-sum-method), though I was inspired by backtracking problems since we "backtrack" on the prefix sums.\n\nFor 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.
['JavaScript']