YSMull
<-- algorithm



原题链接

双递归(25ms)

class Solution {
    public int pathRootSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return (root.val == sum ? 1 : 0)
            + pathRootSum(root.left, sum - root.val)
            + pathRootSum(root.right, sum - root.val);
    }
    public int pathSum(TreeNode root, int sum) {
        if (root == null) return 0;
        return pathRootSum(root, sum)
            + pathSum(root.left, sum)
            + pathSum(root.right, sum);
    }
}

把上面的代码改改,就可以打印出所有路径,但是会超时,因为有个用例有 500500 多万条合法路径。

class Solution {
    public List<List<Integer>> pathSum_with_root(TreeNode root, int targetSum) {
        List<List<Integer>> res = new LinkedList<>();
        pathSum_with_root_0(root, targetSum, new LinkedList<>(), res);
        return res;
    }
    public void pathSum_with_root_0(TreeNode root, int targetSum, List<Integer> cur, List<List<Integer>> res) {
        if (root == null) return;
        cur.add(root.val);
        if (targetSum == root.val) {
            res.add(new LinkedList<>(cur));
        }
        pathSum_with_root_0(root.left, targetSum - root.val, cur, res);
        pathSum_with_root_0(root.right, targetSum - root.val, cur, res);
        cur.remove(cur.size() - 1);
    }
    public List<List<Integer>> pathSum_0(TreeNode root, int targetSum) {
        if (root == null) return new LinkedList<>();
        List<List<Integer>> a = pathSum_with_root(root, targetSum);
        List<List<Integer>> b = pathSum_0(root.left, targetSum);
        List<List<Integer>> c = pathSum_0(root.right, targetSum);
        a.addAll(b);
        a.addAll(c);
        return a;
    }

    public int pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = pathSum_0(root, targetSum);
        // System.out.println(res);
        return res.size();
    }
}

前缀和数组

思路:维护当前路径从根节点到当前结点的所有结点的前缀和的列表。

设从根结点到当前结点的路径为 $[x_1, x_2, \cdots, x_{n-1}, x_n]$
当前结点的前缀和数组为 $[S_1, S_2, \cdots, S_n]$,其中 $S_n$ 为数组 $x_n$ 的前 $n$ 项和。
当我们考察结点 $x_k$ 时,令 $S_0 = 0$,我们遍历 $[S_0, S_1, S_2, \cdots, S_{k-1}]$ 的数组,看存在多少个不同的$m \geq 0$,使得 $S_k-S_m = \mathrm{targetSum}$ ,即有:

\[x_{m+1} + \cdots + x_k = \mathrm{targetSum}\]

也就是说,当我们考察结点 $x_k$ 时,我们寻找有多少个以 $x_k$ 结尾的路径片段其和为 targetSum。

数组实现(15ms)

这个算法的效率已经非常高了

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        List<Integer> sumArr = new ArrayList<>();
        sumArr.add(0);
        return dfs(root, 0, targetSum, sumArr);
    }
    public int dfs(TreeNode root, int currentSum, int target, List<Integer> sumArr) {
        if (root == null) return 0;
        int res = 0;
        currentSum += root.val;
        for (int s: sumArr) {
            if (currentSum - s == target) res += 1;
        }
        sumArr.add(currentSum);
        res += dfs(root.left, currentSum, target, sumArr);
        res += dfs(root.right, currentSum, target, sumArr);
        sumArr.remove(sumArr.size() - 1);
        return res;
    }
}

哈希表实现(3ms)

我们可以去掉每一次遍历前缀和的数组这个过程,使用 HashMap 来维护数组中每一个部分和结果出现的次数。

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Integer, Integer> prefixSumMap = new HashMap<>();
        prefixSumMap.put(0, 1);
        return dfs(root, 0, targetSum, prefixSumMap);
    }
    public int dfs(TreeNode root, int currentSum, int target, Map<Integer, Integer> prefixSumMap) {
        if (root == null) return 0;
        int res = 0;
        currentSum += root.val;
        res += prefixSumMap.getOrDefault(currentSum - target, 0);
        prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);
        res += dfs(root.left, currentSum, target, prefixSumMap);
        res += dfs(root.right, currentSum, target, prefixSumMap);
        prefixSumMap.put(currentSum, prefixSumMap.get(currentSum) - 1);
        return res;
    }
}