2021/05/05
双递归（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_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;
}
}