LeetCode437. 路径总和 III
给定一个二叉树的根节点 root ,和一个整数 targetSum ,求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。 示例1:
输入:root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出:3
解释:和等于 8 的路径有 3 条,如图所示。
前缀和
/**
* 前缀和
*/
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> map = new HashMap<>();
// 当 targetSum 等于某个前缀和时,currPrefix - target = 0,当前节点自己就算做一条符合条件的路径,所以也要计数
map.put(0L, 1);
return preorder(root, map, targetSum, 0);
}
private int preorder(TreeNode node, Map<Long, Integer> map, int target, long currPrefix) {
if (node == null) {
return 0;
}
int num = 0;
// 当前前缀和
currPrefix += node.val;
// 假设当前从根节点 root 到节点 node 的前缀和为 currPrefix
// 则在已保存的 前缀和 中查找是否存在 前缀和 刚好等于 currPrefix − target
// 假设从根节点 root 到节点 node 的路径中存在节点 P(i),到根节点 root 的前缀和为 currPrefix − target
// 则节点 P(i+1) 到 node 的路径上所有节点的和一定为 target
// 1
// /
// 2
// /
// 3
// /
// 4
// 给定值为 target = 5
// prefix(3) = 1 + 2 + 3 = 6
// prefix(1) = 1
// 假设 currPrefix = prefix(3) = 6 即 node = 3
// currPrefix - target = 1 = prefix(1) 即 P(1) , 已经在 map 中,value = 1
// 因此 num = 1 , P(1 + 1) = P(2) 到 P(3) 的路径和为 target = 5
num += map.getOrDefault(currPrefix - target, 0);
// 当前前缀和数量 + 1
map.put(currPrefix, map.getOrDefault(currPrefix, 0) + 1);
num += preorder(node.left, map, target, currPrefix);
num += preorder(node.right, map, target, currPrefix);
// 回溯,防止左边前缀树影响右边前缀树,因为当前节点的前缀和只对子节点有效
// 当前节点可能为父节点的左子节点,切换到父节点的右子节点后左子节点的数据不应当被采用
map.put(currPrefix, map.getOrDefault(currPrefix, 0) - 1);
return num;
}
双递归DFS(超时)
/**
* 一个朴素的做法是搜索以 每个节点 为根的(往下的)所有路径,并对路径总和为 targetSum 的路径进行累加统计
* 在 pathSum2 中搜索所有节点,复杂度为 O(n)
* 在 pathSum2 中对当前节点,使用 dfs 搜索以其为根的所有(往下的)路径,同时累加路径总和为 targetSum 的所有路径,复杂度为 O(n)
*/
public int pathSum2(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
// 对当前节点深搜,获取符合条件的路径和
var num = dfs(root, targetSum);
// 搜索所有节点,累加路径和
num += pathSum2(root.left, targetSum);
num += pathSum2(root.right, targetSum);
return num;
}
private int dfs(TreeNode node, long targetSum) {
if (node == null) {
return 0;
}
int num = 0;
if (node.val == targetSum) {
num++;
}
num += dfs(node.left, targetSum - node.val);
num += dfs(node.right, targetSum - node.val);
return num;
}
题目: 题目链接 参考题解: 官方解答 对前缀和解法的一点解释 【宫水三叶】一题双解 :「DFS」&「前缀和」