CS-Notes Leetcode 题解 - 树 437. Path Sum III Solution 需要更新

Leetcode 题解 - 树 437. Path Sum III Solution 需要更新

Open ptrpengdev opened this issue 2 years ago • 8 comments

437：新test case中 sum值会超过 Integer.MAX_VALUE 导致不过下面这个test case

Input:
[1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000]
0
Output:
2
Expected:
0

新Solution: 可以把 pathSumStartWithRoot input 的int sum改成 long sum

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    int ret = pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    return ret;
}
// sum type 从int改成long
private int pathSumStartWithRoot(TreeNode root, long sum) {
    if (root == null) return 0;
    int ret = 0;
    if (root.val == sum) ret++;
    ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
    return ret;
}