[L437] 前缀和

参考 https://leetcode.cn/problems/path-sum-iii/solution/qian-zhui-he-di-gui-hui-su-by-shi-huo-de-xia-tian/

前缀和：顾名思义，就是从根节点到此节点的和

思路：

拿图中的10-5-3举例子

• 在节点10时，前缀和为10
• 在节点5时，前缀和为15
• 在节点3时，前缀和为18

18-10 = 8，也就是我们所需要的路径和8，这个8就代表了5-3段的和为8，也就是这个题的解之一

实现

• 用curSum表示目前的前缀和

• 用n表示需要的路径总和

• 那么当到达一个节点时，需要检查curSum-n这样的前缀和是否存在，如果存在那么curSum-(curSum-n) = n，也就是存在一个路径总和为n，存在一个解，如果有多个这样的前缀和，那么就存在多个解。

• 显然我们需要一个容器来存储这样的前缀和，方便在每个节点时检查是否存在curSum-n的前缀和，这里使用Map

• 对树的遍历使用递归+回溯的方式

• 针对这个题有一个坑
  在int时，2000000000+1000000000=-294967296，所以用long

代码

class Solution {
    Map<Long,Integer> container = new HashMap<>();
    int n = 0;
    public  int pathSum(TreeNode root, int targetSum) {
        n = targetSum;
        container.put(0L,1);
        return dfs(root,0);
    }

    public int dfs(TreeNode node,long curSum){
        if(node==null) return 0;
        curSum = curSum+node.val;//得到新的前缀和
        if(curSum<Integer.MIN_VALUE||curSum>Integer.MAX_VALUE) return 0; // 对大数的处理
        int res = container.getOrDefault(curSum-n,0);//从根到这个节点，多少个前缀和为curSum-n，因为curSum-(curSum-n) = n 代表中间这段和为n
        container.put(curSum,container.getOrDefault(curSum,0)+1);//将这个节点的前缀和记录到container中，方便下次遍历
        int left = dfs(node.right,curSum);//左子树的所有解
        int right = dfs(node.left,curSum);//右子树的所有解
        container.put(curSum,container.getOrDefault(curSum,0)-1);//回溯，恢复原来的状态
        return left+right+res;//返回以这个节点为根的子树的所有解
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

上面是题解，自己用的还是朴素暴力
recur 是遍历每个树
searchPath 是以node为根，遍历子树寻找路径

class Solution {
     int sum = 0;
     int targetSum = 0;
    public  int pathSum(TreeNode root, int targetSum) {
        this.targetSum = targetSum;
        recur(root);
        return sum;
    }
    public  void recur(TreeNode node){
        if(node==null) return;
        searchPath(node,0);
        recur(node.left);
        recur(node.right);
    }
    public  void searchPath(TreeNode node,long value){
        if(node==null)return;
        value = node.val+value;
        if(value>Integer.MAX_VALUE||value<Integer.MIN_VALUE)return;
        if(value==targetSum){
            sum++;
        }
        searchPath(node.left,value);
        searchPath(node.right,value);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26