Concise JavaScript O(n) solution using map


  • 2
    var pathSum = function(root, sum, presums = { '0': 1 }, prev = 0) {
        if (!root) return 0;
        let curr = prev + root.val;
        presums[curr] = (presums[curr] || 0) + 1;
        let res = (presums[curr - sum] || 0) - !sum;
        res += pathSum(root.left, sum, presums, curr) + pathSum(root.right, sum, presums, curr);
        presums[curr]--;
        return res;
    };
    

    This turns out to be the same as @tankztc's solution here, though I was inspired by backtracking problems since we "backtrack" on the prefix sums.

    For a balanced tree we use O(log n) space, otherwise as bad as O(n). Also, I think the "easy" categorization should be changed to "pain in the..." :P.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.