112. Sum of paths

var hasPathSum = function(root, targetSum) {
    if (root === null) return false
    const res = targetSum - root.val
    if (root.left === null && root.right === null) return res == 0 ? true : false
    else return hasPathSum(root.left, res) || hasPathSum(root.right, res)
};
Copy the code

113. Sum of paths II

var pathSum = function(root, targetSum) {
    if (root === null) return []
    let res = [], way = []

    const dfs = (root, targetSum) = > {
        way.push(root.val)
        targetSum -= root.val
        if (targetSum === 0 && root.left === null && root.right === null) {
            res.push([...way])
        }
        root.left && dfs(root.left, targetSum)
        root.right && dfs(root.right, targetSum)
        let curr = way.pop()      / / back
        targetSum += curr
    }
    dfs(root, targetSum)
    return res
};
Copy the code

437. Sum of paths III

var pathSum = function(root, targetSum) {
    const prefix = new Map()
    prefix.set(0.1)
    return dfs(root, prefix, 0, targetSum)
};

const dfs = (root, prefix, curr, targetSum) = > {
    if (root === null) return 0
    let ret = 0
    curr += root.val

    ret = prefix.get(curr - targetSum) || 0
    prefix.set(curr, (prefix.get(curr) || 0) + 1)    // join the hash table
    ret += dfs(root.left, prefix, curr, targetSum)
    ret += dfs(root.right, prefix, curr, targetSum)
    prefix.set(curr, (prefix.get(curr) || 0) - 1)    
    // Delete the record. Because at the end of the day, back on the floor,
    // Indicates that the current level of recursion is complete, to return to the previous level,
   // Clear the state of this layer, since map is passing an object,
   // The state has been changed, and in order not to affect the subsequent recursive traversal, we need to clear this layer

    return ret
}
Copy the code

560. And are subarrays of K

var subarraySum = function(nums, k) {
    const mp = new Map(a); mp.set(0.1);
    let count = 0, pre = 0;
    for (const x of nums) {
        pre += x;
        if (mp.has(pre - k)) {
            count += mp.get(pre - k);
        }
        mp.set(pre, (mp.get(pre) || 0) + 1);
    }
    return count;
};
Copy the code