437. Path Sum III

Description

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

Solution

Solution 1

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * Traverse the binary tree with Depth-First Search (DFS) algorithm (preorder)
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    "use strict";
    let result = 0;
    function findPath(node, tmpSum) {
        if (node) {
            tmpSum += node.val;
            if (tmpSum === sum) {
                result++;
            }
            findPath(node.left, tmpSum);
            findPath(node.right, tmpSum);
        }
    }
    function dfs(node) {
        if (node) {
            findPath(node, 0);
            dfs(node.left);
            dfs(node.right);
        }
    }
    dfs(root);
    return result;
};

Solution 2

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * Traverse the binary tree with Depth-First Search (DFS) algorithm (preorder)
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    "use strict";
    let result = 0;
    function dfs(node, pathSum, table) {
        if (node) {
            pathSum += node.val;
            if (table[pathSum-sum]) {
                result += table[pathSum-sum];
            }
            if (table[pathSum] === undefined) {
                table[pathSum] = 0;
            }
            table[pathSum]++;
            dfs(node.left, pathSum, table);
            dfs(node.right, pathSum, table);
            table[pathSum]--;
        }
    }
    dfs(root, 0, { 0: 1 });
    return result;
};