hot100 437.路径总和Ⅲ

思路：前缀和解法，利用前缀和求节点值之和等于targetSum的路径的数目（满足路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的，只能从父节点到子节点）。

一、前缀和定义：

1.定义：一个节点的前缀和就是该节点到根之间的路径和。

2.举例：如下图所示。

（1）节点4的前缀和为：1 + 2 + 4 = 7。

（2）节点8的前缀和为：1 + 2 + 4 + 8 = 15。

（3）节点9的前缀和为：1 + 2 + 5 + 9 = 17。

二、本题中前缀和的作用：两节点间的路径和即为两节点的前缀和之差。

1.举例：

（1）如下图所示：假如题目给定数值为5，节点1的前缀和为1，节点3的前缀和为1 + 2 + 3 = 6。

（2）prefix(3) - prefix(1) == 5。

（3）所以节点1到节点3之间，有一条符合要求的路径2->3。

2.利用前缀和简化问题：我们只需要遍历整棵树一次，记录每个节点的前缀和，并查询该节点的祖先节点中符合条件的个数，将这个数量加到最终结果上。

三、HashMap存储数据：key存储前缀和，value是该前缀和的节点数量，记录数量是因为有出现重复路径的可能。

举例：如下图所示，改图中前缀和为1的节点有两个，分别是0和1，所以路径和为2的路径数就有两条，分别是0->2和2。

.

四、恢复状态的意义：

1.题目要求：路径方向必须是向下的，即只能从父节点到子节点。当计算两个节点的前缀和的差值时，其中一个节点必须是另一个节点的祖先节点。

2.换句话说，当我们把一个节点的前缀和信息更新到map里时，它应当只对其子节点们生效。

举例：下图中有两个值为2的节点A，B。

（1）当遍历到最右方的节点6时，对于它来说，此时的前缀和为2的节点只该有B，因为A并不是节点6的祖先节点。

（2）如果不做状态恢复的话，当遍历右子树时，左子树中A的信息仍会保留在map中，那么此时节点6就会认为A，B都是可追溯到的节点，从而产生错误。

3.状态恢复代码的作用：在遍历完一个节点的所有子节点后，将其从map中除去。

五、核心思想：寻找从根节点到当前节点的路径上，是否存在某个前缀和curSum - target。如果存在，则说明从那个前缀和对应的节点到当前节点的路径和正好等于target。

即：curSum - (curSum - target) == target。

附代码：

class Solution { Map<Long,Integer> prefixMap; int target; public int pathSum(TreeNode root, int targetSum) { prefixMap = new HashMap<>(); target = targetSum; // key表示前缀和，value表示前缀和为这个值的路径的数量。 // 初始化，表示空路径的前缀和为0，出现了1次，为了处理从根节点开始的路径 prefixMap.put(0L,1); return recur(root,0L); } // recur函数，用于遍历二叉树，对于每个节点，记录前缀和的同时，返回当前找到和为target的路径的数量 // curSum表示node节点之前的前缀和 private int recur(TreeNode node,Long curSum){ if(node == null){ return 0; } int res = 0; // 记录路径数量 curSum += node.val; // 根节点到当前节点的路径和 // 如果curSum - target在prefixMap中存在，则说明存在某个节点到当前节点的路径和等于target // curSum - (curSum - target) = target // 比如：target = 8，如果之前存在前缀和 = 5，且当前前缀和 = 13，那么13 - 5 = 8，说明从那个节点到当前节点的路径和为8 res += prefixMap.getOrDefault(curSum - target,0); // 把当前节点的前缀和也加入到哈希表中，value加1 prefixMap.put(curSum,prefixMap.getOrDefault(curSum,0) + 1); // 递归处理子树 int left = recur(node.left,curSum); int right = recur(node.right,curSum); res = res + left + right; // 所有找到的路径数量总和即为总的路径数量 // 恢复状态 prefixMap.put(curSum,prefixMap.get(curSum) - 1); // 当前节点处理完后，要返回到父节点，当前节点的前缀和不应该影响其他分支的统计。因此在遍历完一个节点的所有子节点后，将其从map中除去 return res; } }