给定一颗二叉树和一个整数 sum，求累加和为 sum 的最长路径长度。路径是指从某个节点往下，每次最多选择一个孩子节点或者不选所形成的节点链
求和为指定值的最长路径，我们可以把每一条路径看作一个数组，然后对他进行求指定值，使用前缀和的方法可以很好的实现，也可以使用正常的遍历，对每一个结点进行计算
前缀和
public static int pathSum(TreeNode root, int targetSum) {
// key为路径和，value为路径和最早出现的层数
Map map = new HashMap();
map.put(0, 0);
return preOrder(root,targetSum,map,0,1,0);
}
public static int preOrder(TreeNode root,int targetSum,
Map map,int preSum,int level,int maxLen){
if(root == null) {
return maxLen;
}
// 计算从根节点到当前结点的路径和
preSum += root.value;
// 这里需要提前将当前节点对应的层数加入哈希表中，因为有可能我们当前节点对应的前缀和就是presum-targetSum
if(!map.containsKey(preSum)) {
// 如果哈希表中没有preSum，则将当前preSum和其第一次出现的位置加入哈希表中
map.put(preSum, level);
}
if(map.containsKey(preSum - targetSum)) {
// 计算最大长度
maxLen = Math.max(level - map.get(preSum - targetSum), maxLen);
}
// 计算当前结点的左右节点
maxLen = preOrder(root.left,targetSum,map,preSum,level + 1,maxLen);
maxLen = preOrder(root.right,targetSum,map,preSum,level + 1,maxLen);
/*
* 这一步的操作是为了清除map表中的当前结点的数据，因为当前节点的子树已经处理完了，要返回其父节点，对父节点的子树进行处理，
* 如果当前节点的数据还在map里面，后面在其他子树中可能会有一样的数据key和value，简单地说就是为了处理一段路径的时候，不会被
* 其他路径上的数据影响
* */
if(map.get(preSum) == level) {
map.remove(preSum);
}
return maxLen;
}
代码解析：
这个思路可以理解为将每一个结点到叶子节点的路径当作数组来求最大子数组长度
使用前缀和加哈希表优化，我们遍历树路径的时候，计算根节点到当前节点的前缀和，我们将前缀和作为key，当前前缀和当前节点位置作为value存入哈希表中，当我们每一次遍历数组元素的时候，判断presum-k在哈希表中有没有对应的数据，如果有，从当前位置到哈希表中对应的位置之间的差值就是对应的路径的长度（ 通过sum-k可以得到子数组的长度是因为，我们计算k的时候是使用preSum[i]-preSum[j] = k，那么preSum[j] = preSum[i]-k，所以当哈希表中存在sum-k就表示当前前缀和数组中存在子数组和为k），遍历完数组后得到的最大长度就是最大子路径长度
注意：我们将每一个结点到叶子节点的路径当作数组进行处理，但是当我们从一条路径跳出来去其他路径计算的时候，原来路径的数据会对现在的路径计算进行影响，所以每次退出当前路径（其实也就是当前节点到了叶子节点）的时候需要将当前节点的数据从哈希表中删除
看见连续累加和为指定值就要想到使用前缀和。
Original: https://www.cnblogs.com/foldn/p/15969876.html
Author: foldn
Title: 在二叉树中找到累加和为指定值的最长路径（前缀和）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/579746/
转载文章受原作者版权保护。转载请注明原作者出处！