```
int dfs(TreeNode* node, vector<int> &preSum, int iEnd, int sum)
{
int count=0;
if(node == NULL) return 0;
if(node->val == sum) count++;
for(int i=0; i <= iEnd; ++i) {
preSum[i] += node->val;
if(preSum[i] == sum) count++;
}
preSum[iEnd+1] = node->val;
count += dfs(node->left, preSum, iEnd+1, sum);
count += dfs(node->right, preSum, iEnd+1, sum);
for(int i=0; i<=iEnd; ++i)
preSum[i] -= node->val;
return count;
}
int pathSum(TreeNode* root, int sum) {
vector<int> preSum(1000, 0);
return dfs(root, preSum, -1, sum);
}
```