看完题目我就拿直接用递归写了如下代码：

class Solution {private int ans;public int pathSum(TreeNode root, int targetSum) {ans =0;dfs(root, targetSum, 0);return ans;}public void dfs(TreeNode root, int targetSum, int sum){if(root == null)return;sum += root.val;if(sum == targetSum)ans++;dfs(root.left, targetSum, sum);dfs(root.left, targetSum, 0);dfs(root.right, targetSum, sum);dfs(root.right, targetSum, 0);return;}
}

 dfs方法中的参数sum表示从前面某个节点到上一个节点的和，拿这个sum加上当前节点的值如果等于targetSum那么答案数+1，然后可以把现在的sum往下面传递，也可以传一个0下去表示从下一个节点开始计算和，然后示例过了，测试用例没过，因为这样的话重复计算了多个答案，比如一个全右的树1，2，3，4，5，target=3，那么在dfs1的时候，传了sum等于0，然后dfs2的时候又传了sum等于0，然后dfs3，这条1，2，3的路径给算进去了，所以这样是不行的。然后自己想了一会没思路就直接看了题解，

题解的第一种做法用的就是深度优先，但和我的不一样，他用了两层递归。

首先定义第一个递归方法：

public int rootSum(TreeNode root, int targetSum)

它表示以root为起点的路径中，和为target的个数。在主函数中递归遍历每个节点，把这些节点的rootSum加起来。以下是方法一的代码：

class Solution {public int pathSum(TreeNode root, int targetSum) {if(root == null)return 0;int ans =0;ans+=rootSum(root,targetSum);ans+= pathSum(root.left, targetSum);ans+=pathSum(root.right, targetSum);return ans;}public int rootSum(TreeNode root, long targetSum){if(root == null)return 0;int ret = 0;if(root.val == targetSum) ret++;ret+= dfs(root.left, targetSum-root.val);ret+= dfs(root.right, targetSum-root.val);return ret;}
}

在rootSum()方法中要算以root为起点和为targetSum的路径数，就是算以root.left为起点和为targetSum-root.val的路径数加上以root.right为起点，和为targetSum-root.val的路径数。当root.val=targetSum时+1。然后主函数递归遍历每个节点，使得每个节点都调用一遍rootSum()方法。

方法一的时间复杂度时O(n2)很高，做了很多重复的计算。方法二是利用了HashMap里面存放前缀和来减少遍历次数。以下是方法二代码：

class Solution {public int pathSum(TreeNode root, int targetSum) {Map<Long, Integer> prefix = new HashMap<Long, Integer>();prefix.put(0L, 1);return dfs(root, prefix, 0, targetSum);}public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {if (root == null) {return 0;}int ret = 0;curr += root.val;ret = prefix.getOrDefault(curr - targetSum, 0);prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);ret += dfs(root.left, prefix, curr, targetSum);ret += dfs(root.right, prefix, curr, targetSum);prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);return ret;}
}

Map<Long, Integer> prefix里面存的是，路径和为key的数量value，long curr表示从根节点到当前节点的和，这一点必须明白。

假如根节点是root，我们正在访问的节点是node，这条路径就是root->p1->p2->..->pk..->node。计算到node的时候从root到node的和是curr，那么我们只要找到前面的一个节点pk,它的curr1是curr-targetNum,那么从pk到node的和就是tagetNum。我们不需要找到这个pk，只需要知道这条路径上有多少个这样的pk就行。所以我们的HashMap中存放的是和为key的数量而不是节点。

理解了这个看dfs方法就比较容易了。

ret = prefix.getOrDefault(curr - targetSum, 0);

这个HashMap的getOrDefault方法是先去get这个key这里是curr-targetSum。如果没有这个key就返回默认值这里是0。这样就拿到了以当前节点为终点和为target的路径的数量，

prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);

然后再把从root到当前节点的和放进map里面，然后递归遍历子节点。因为这个prefix的map是全局都在用的，所以当你把当前节点遍历完了你得回溯，把自己给移出去，因为递归回到前面的时候，前面的节点不能用后面节点的前缀和，所以要把这个前缀和的数量-1。