https://leetcode.com/problems/path-sum-iii/

pathSumIII.js

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
// Brute Force
// Each node is inspected once by d nodes above
// it. In a balanced tree there are log(n) nodes
// so in a balanced tree, this will run in O(nlog(n)).
// An unbalanced tree will act like a linked list, 
// so each node is touched by n nodes preceding it,
// giving a worst-case O(n^2).
var pathSum = function(root, sum) {
    
    const search = (node, target) => {
        if(!node) return 0;
        const remainder = target - node.val;
        let result = remainder === 0 ? 1 : 0;
        result += search(node.left, remainder);
        result += search(node.right, remainder);
        return result;
    };
    
    const origins = (node) => {
        if(!node) return 0;
        let result = search(node, sum);
        result += origins(node.left);
        result += origins(node.right);
        return result;
    }
    
    return origins(root, sum);
};


// backtracking with cache: O(n)
var pathSum = function(root, sum) {

    const seenValues = {};
    
    const inner = (node, precedingSum) => {
        
        if(!node) return 0;
        const total = precedingSum + node.val;
        const diff = total - sum;
        
        /* Two cases in which this node could be part of a result. */
        // 1. There is a path including all nodes from the root to here
        let result = diff === 0 ? 1 : 0;
        // 2. There is a path from one of the root's descendents to here.
        result += seenValues[diff] || 0; // Every time we have previously had a 
        // total equal to this diff, there is a path of sum `sum` from the node
        // following the point at which we saw that diff to this one
        
        seenValues[total] = seenValues[total] ? seenValues[total] + 1 : 1; // update seenValues
        
        result = result + inner(node.left, total) + inner(node.right, total); // search recursively
        
        seenValues[total]--; // backtrack: clean up seenValues
        return result;
    };
    
    return inner(root, 0);
};