https://leetcode.cn/problems/path-sum-iii/
image.png
前缀和
/**
*
* pathSum iii:只要路径向下即可,不要求起终点为root和leaf:返回看加起来 == sum的路径的个数
*
* 前缀和
*/
public int pathSumIII(TreeNode root, int target) {
if(root == null) {
return 0;
}
Map<Integer, Integer> prefix = new HashMap<>();
prefix.put(0, 1);
return helper(root, target, prefix, 0);
}
private int helper(TreeNode root, int target, Map<Integer, Integer> prefix, int curSum) {
if(root == null) {
return 0;
}
int res = 0;
curSum += root.val;
// 此前存在路径的个数(A点 和 当前点 的差值是target,那么 A-当前点是有效路径)
res += prefix.getOrDefault(curSum-target, 0);
// 回溯
prefix.put(curSum, prefix.getOrDefault(curSum, 0) + 1);
res += helper(root.left, target, prefix, curSum);
res += helper(root.right, target, prefix, curSum);
prefix.put(curSum, prefix.getOrDefault(curSum, 0) - 1);
return res;
}
网友评论