437. 路径总和 III

题目：给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

方法一：遍历出每个结点开头的路径，并计算以这个结点开头的符合条件的路径有多少。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @param {number} targetSum* @return {number}*///主函数var pathSum = function(root, targetSum) {if(root===null){return 0;}let ret = rootSum(root,targetSum);ret+=pathSum(root.left,targetSum);ret+=pathSum(root.right,targetSum);return ret;
};//用于计算某个结点的所有路径const rootSum = (root,targetSum)=>{let ret = 0;if(root===null){return 0;}const val = root.val;if(val===targetSum){ret++;}ret += rootSum(root.left,targetSum-val);ret += rootSum(root.right,targetSum-val);return ret;}

方法二:前缀和

        因为原来的寻找ret是用递归的方法，相当于套了两层for，但是现在在一次递归中，就可以找到答案。减少的时间复杂度在于前缀和免去了方法一种对重复子节点的计算。

/*** Definition for a binary tree node.* function TreeNode(val, left, right) {*     this.val = (val===undefined ? 0 : val)*     this.left = (left===undefined ? null : left)*     this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @param {number} targetSum* @return {number}*/
var pathSum = function(root, targetSum) {const hash = new Map();hash.set(0,1);return dfs(root,hash,0,targetSum);
};const dfs = (root,hash,cur_sum,targetSum)=>{ //hash记录前面出现过的前缀和出现的次数if(root===null){return 0;}let res = 0;cur_sum+=root.val;//更新前缀和res = hash.get(cur_sum-targetSum) || 0;//将当前的前缀和更新到hashhash.set(cur_sum,(hash.get(cur_sum) || 0)+1);res += dfs(root.left,hash,cur_sum,targetSum);res += dfs(root.right,hash,cur_sum,targetSum);//遍历完当前节点需要取消hash中的记录hash.set(cur_sum,(hash.get(cur_sum) || 0) - 1)return res;
}