https://leetcode.com/problems/path-sum-iii/
理解比较困难，可以先看https://www.cnblogs.com/albert67/p/10416402.html
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
HashMap<Integer,Integer> preSum=new HashMap<>();
preSum.put(0,1);// 当键值等于0，说明curSum==sum，所以把设为1
return helper(root,0,sum,preSum);
} public int helper(TreeNode n,int curSum,int target,HashMap<Integer,Integer> preSum){
if(n==null)return 0;
curSum+=n.val;
int res=preSum.getOrDefault(curSum-target,0);
preSum.put(curSum,preSum.getOrDefault(curSum,0)+1);
res+=helper(n.left,curSum,target,preSum)+helper(n.right,curSum,target,preSum);
preSum.put(curSum,preSum.get(curSum)-1);
return res;
}
}
递归比较慢，但很容易理解
class Solution {
public int pathSum(TreeNode root, int sum) {
if(root==null)return 0;
return add(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);
}
public int add(TreeNode n,int sum){
if(n==null)return 0;
return (sum-n.val==0?1:0)+add(n.left,sum-n.val)+add(n.right,sum-n.val);
}
}