437. Path Sum III

[Tcdian]

437. Path Sum III

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

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

[Tcdian]

Solution

• JavaScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function(root, sum) {
    const cache = new Map([[0, 1]]);
    let prefixSum = 0;
    let result = 0;
    dfs(root);
    return result;

    function dfs(root) {
        if (root === null) {
            return;
        }
        prefixSum += root.val;
        if (cache.has(prefixSum - sum)) {
            result += cache.get(prefixSum - sum);
        }
        cache.set(prefixSum, (cache.get(prefixSum) || 0) + 1);
        dfs(root.left);
        dfs(root.right);
        cache.set(prefixSum, cache.get(prefixSum) - 1);
        prefixSum -= root.val;
    }
};

• TypeScript Solution

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function pathSum(root: TreeNode | null, sum: number): number {
    const cache: Map<number, number> = new Map([[0, 1]]);
    let prefixSum = 0;
    let result = 0;
    dfs(root);
    return result;

    function dfs(root: TreeNode | null) {
        if (root === null) {
            return;
        }
        prefixSum += root.val;
        if (cache.has(prefixSum - sum)) {
            result += cache.get(prefixSum - sum) as number;
        }
        cache.set(prefixSum, (cache.get(prefixSum) || 0) + 1);
        dfs(root.left);
        dfs(root.right);
        cache.set(prefixSum, cache.get(prefixSum) as number - 1);
        prefixSum -= root.val;
    }
};