路径总和III
问题
js
给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
答案
js
* @param {TreeNode} root
* @param {number} targetSum
* @return {number}
*/
var pathSum = function(root, targetSum) {
let map=new Map();
let res=0;
map.set(0,1);
let dfs=(root,sum)=>{
if(!root) return;
sum+=root.val;
if(map.has(sum-targetSum)){
res+=map.get(sum-targetSum);
}
map.set(sum,(map.get(sum)||0)+1);
dfs(root.left,sum);
dfs(root.right,sum);
map.set(sum,map.get(sum)-1);
}
dfs(root,0);
return res;
};
扩展
前缀和+哈希表
js
// 回溯:用完以后把当前前缀和删一份,避免影响兄弟节点的计算
map.set(sum, map.get(sum) - 1);