Skip to content

路径总和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);