力扣hot100：路径总和III

题目描述：

思路：

本题和“和为k的子数组 有异曲同工之妙”，思路也相似。可以用一个哈希表去存储每条路径的和，两条路径和只差即为中间路径的和。

可以用递归的方式向下遍历这颗树，定义一个s，表示目前路径的和，每走一个节点就把节点值加入s，然后判断哈希表中是否存在s-targetSum，如果存在说明找到了和为targetSum的路径，不存在就把更新哈希表。

需要注意的是，左右叶子节点递归完之后要回溯哈希表，以免对其他分支的技术产生问题。

代码：

class Solution { private int ans=0; public int pathSum(TreeNode root, int targetSum) { Map<Long,Integer> cnt=new HashMap<>(); cnt.put(0L,1); dfs(root,0,targetSum,cnt); return ans; } private void dfs(TreeNode node,long s,int targetSum,Map<Long,Integer> cnt){ if(node==null){ return; } s+=node.val; ans+=cnt.getOrDefault(s-targetSum,0); cnt.merge(s,1,Integer::sum); dfs(node.right,s,targetSum,cnt); dfs(node.left,s,targetSum,cnt); cnt.merge(s,-1,Integer::sum); } }