题面
核心思想
树上的前缀和o(n)
当前的前缀和:curSum
前面的前缀和:preSum
如果 curSum - preSum == target
就说明有一段区间和为target,preSum出现了几次就有几段区间,所以用map存储前缀和出现的次数
代码
class Solution {
private int res = 0;
// 437. 路径总和 III
public int pathSum(TreeNode root, int targetSum) {
//前缀和
HashMap<Long, Integer> cnt = new HashMap<Long,Integer>();
cnt.put(0L, 1);
pathSumHelper(root,cnt, 0L, targetSum);
return res;
}
private void pathSumHelper(TreeNode cur, HashMap<Long, Integer> cnt,Long sum, int targetSum){
if(cur == null)
return;
//当前前缀和
sum += cur.val;
//查找是否有答案
int resTmp = cnt.getOrDefault(sum - targetSum, 0);
if(resTmp != 0)
System.out.println(cur.val);
res += resTmp;
//put一定要在计算答案之后 否则查找前缀和的时候可能查到自己 但此时自己是不算的
cnt.put(sum, cnt.getOrDefault(sum, 0) + 1);
//左子树
pathSumHelper(cur.left, cnt, sum, targetSum);
//右子树
pathSumHelper(cur.right, cnt, sum, targetSum);
// 退出到当前节点后-1,因为map引用的是同一块内存地址 否则会出现左子树到右子树这样的区间 不符合题意
cnt.put(sum, cnt.get(sum) - 1);
}
}
标签:cnt,前缀,int,sum,cur,targetSum,437,III,总和
From: https://www.cnblogs.com/ganyq/p/18119813