437. 路径总和 III (Java) LeeCode

解题思路：

本体需要结合 前缀和数组的技巧外加DFS遍历树，引入HashMap。

对于前缀和，穷举一个数组中所有的数组可能如下

for (int i = 1; i <= n; i++)
    for (int j = 0; j < i; j++)
        if (preSumCount[i] - preSumCount[j] == targetSum)
            count++;

我们利用HashMap换个思路，把相差为targetSum的 preSumCount[j] 储存起来 preSumCount[j] = preSumCount[i] - targetSum

也就是下面的
res += preSumCount.getOrDefault(pathSum - targetSum, 0);

class Solution {
	//储存前缀和
    HashMap preSumCount = new HashMap<>();

    int pathSum, targetSum;
    int res = 0;

    public int pathSum(TreeNode root, int targetSum) {

        if(root == null)return 0;

        this.pathSum = 0;
        this.targetSum = targetSum;
        this.preSumCount.put(0,1);
        traverse(root);
        return res;
        

    }

    void traverse(TreeNode root){

        if(root == null) return ;
		//前缀和
        pathSum += root.val;
		
        res += preSumCount.getOrDefault(pathSum - targetSum, 0);
		//更新每一个前缀和出现的次数
        preSumCount.put(pathSum, preSumCount.getOrDefault(pathSum,0) + 1);
		//进入下一层
        traverse(root.left);
        traverse(root.right);
		//维护前缀和数组（回到本层移除当前节点和前缀和数量）
        preSumCount.put(pathSum, preSumCount.get(pathSum) - 1);
        pathSum -= root.val;
        
    }
}