LeetCode 437. 路径总和 III
给定一个二叉树,它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。
二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。
示例:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11
前缀和 + 回溯
前缀和:从根到当前节点的路径上,所有节点的元素的和(包含当前元素)。
若处于同一路径上的节点 A 和 B ,若 “节点 B 的前缀和 - 节点 A 的前缀和 = target”,则说明节点 A 和 B 之间的元素之和为 target ,即节点 A 和 B 之间的这段路径为满足题目要求的路径。
可利用回溯遍历整棵树,并用上述方法统计出满足要求的路径数量。
class Solution {
public int pathSum(TreeNode root, int targetSum) {
// 保存路径中的前缀和,key是前缀和, value是大小为key的前缀和出现的次数
Map<Integer, Integer> prefixSumMap = new HashMap<>();
prefixSumMap.put(0, 1); // 处理某条路径的 currsum 恰好等于 targetSum 的情况
return recur(root, prefixSumMap, targetSum, 0);
}
private int recur(TreeNode root, Map<Integer, Integer> prefixSumMap, int targetSum, int currSum) {
if (root == null) return 0;
int res = 0;
currSum += root.val; // 从根到当前节点的前缀和
// 若Map中前缀和为currSum - targetSum的出现次数大于0,说明中间存在和为targetSum的路径
res += prefixSumMap.getOrDefault(currSum - targetSum, 0);
// 保存当前路径的前缀和
prefixSumMap.put(currSum, prefixSumMap.getOrDefault(currSum, 0) + 1);
res += recur(root.left, prefixSumMap, targetSum, currSum);
res += recur(root.right, prefixSumMap, targetSum, currSum);
// 向上回溯,删除当前路径,恢复状态
prefixSumMap.put(currSum, prefixSumMap.get(currSum) - 1);
return res;
}
}
- 时间复杂度:O(n) ,树的每个节点遍历一次
- 空间复杂度:O(n)