Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

437. Path Sum III #289

Open
Tcdian opened this issue Aug 8, 2020 · 1 comment
Open

437. Path Sum III #289

Tcdian opened this issue Aug 8, 2020 · 1 comment

Comments

@Tcdian
Copy link
Owner

Tcdian commented Aug 8, 2020

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
Copy link
Owner Author

Tcdian commented Aug 8, 2020

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;
    }
};

@Tcdian Tcdian removed the Classic label Jul 30, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant