[Leetcode] 437. Path Sum III | 路径总和 III

yPhantom 2020年02月03日 26次浏览

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

这道题与560题几乎一模一样。给出一棵树,让找出该树中从父到子的路径中结点和为target一共有多少条路径。而560题呢,是求一个数组中和为target的子数组。解法都是HashMap+PreSum,甚至代码结构都一致。

我们还是以累加和Sum - target为hashmap的key,怎么理解呢?我们以当前结点为一条路径的末(终)结点,这条路径的和为sum,如果hashmap中已经保存了一条路径,和为sum-target。那么从这条路径的末结点到当前这条结点的和必为target。因此我们只要找sum-target有多少条路径就行了。代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        return helper(root, 0, sum, map);
    }
    
    private int helper(TreeNode root, int cur, int target, Map<Integer, Integer> map) {
        if (root == null) {
            return 0;
        }
        cur += root.val;
        int res = map.getOrDefault(cur - target, 0);
        map.put(cur, map.getOrDefault(cur, 0) + 1);
        res += helper(root.left, cur, target, map) + helper(root.right, cur, target, map);
        map.put(cur, map.get(cur) - 1);
        return res;
    }
}

map.put(0, 1)代表如果当前结点的和正好就是target,那么次数就是1。我猜所有PreSum + HashMap的题都要这样初始化一下。

整个代码流程就是,首先得到当前路径的总和,然后得到cur - target的次数,然后递增当前和的次数,进行左子树和右子树的遍历,然后为了不影响其他路径的计算(累加和-target必须要是一条路径),将当前和的次数还原。返回res。

这道题对于知晓这种方法的人应该是easy难度,对于不知道的......呵呵

参考链接

17 ms O(n) java Prefix sum method

相似题目

560. Subarray Sum Equals K