剑指offer-80、⼆叉树中和为某⼀值的路径(二)
题⽬描述给定⼀个⼆叉树root和⼀个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
[*]该题路径定义不需要从根节点开始，也不需要在叶⼦节点结束，但是⼀定是从⽗亲节点往下到孩⼦节点
[*]总节点数⽬为 n
[*]保证最后返回的路径个数在整形范围内
假如⼆叉树 root 为 {1,2,3,4,5,4,3,#,#,-1} ， sum=6 ，那么总共如下所示，
思路及解答
双重递归法（暴力解法）
外层递归遍历所有节点作为起点，内层递归计算从该点向下的路径和
public class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
// 以当前节点为起点的路径数 + 左右子树的路径数
return countPaths(root, targetSum) +
pathSum(root.left, targetSum) +
pathSum(root.right, targetSum);
}
/**
* 计算以当前节点为起点的路径数
*/
private int countPaths(TreeNode node, long targetSum) {
if (node == null) return 0;
int count = 0;
// 如果当前节点值等于目标值，找到一条路径
if (node.val == targetSum) {
count++;
}
// 递归计算左右子树
count += countPaths(node.left, targetSum - node.val);
count += countPaths(node.right, targetSum - node.val);
return count;
}
}
[*]时间复杂度：O(n²)，最坏情况下每个节点都要递归遍历其子树
[*]空间复杂度：O(n)，递归栈深度
前缀和哈希表（最优解）
从根节点到当前节点的路径和curSum，查找curSum-targetSum是否存在
前缀和核心思想：
[*]路径和 = 当前前缀和 - 之前某个前缀和
[*]curSum - targetSum是否存在于前缀和哈希表中
[*]如果存在，说明从那个节点到当前节点的路径和为targetSum
执行示例（树，sum=8）：
从根到节点3：前缀和=10+5+3=18
targetSum=8 → 查找18-8=10是否存在
哈希表中有10（根节点）→ 找到路径：5->3import java.util.HashMap;
public class Solution {
public int pathSum(TreeNode root, int targetSum) {
// 哈希表存储前缀和及其出现次数
HashMap<Long, Integer> prefixSum = new HashMap<>();
prefixSum.put(0L, 1); // 初始前缀和为0，出现1次
return dfs(root, 0, targetSum, prefixSum);
}
private int dfs(TreeNode node, long curSum, int targetSum,
HashMap<Long, Integer> prefixSum) {
if (node == null) return 0;
// 计算从根节点到当前节点的前缀和
curSum += node.val;
// 查找前缀和中是否存在curSum - targetSum
// 如果存在，说明从那个节点到当前节点的路径和为targetSum
int count = prefixSum.getOrDefault(curSum - targetSum, 0);
// 将当前前缀和加入哈希表
prefixSum.put(curSum, prefixSum.getOrDefault(curSum, 0) + 1);
// 递归处理左右子树
count += dfs(node.left, curSum, targetSum, prefixSum);
count += dfs(node.right, curSum, targetSum, prefixSum);
// 回溯：移除当前前缀和，避免影响其他分支
prefixSum.put(curSum, prefixSum.get(curSum) - 1);
return count;
}
}
[*]时间复杂度：O(n)，每个节点只访问一次
[*]空间复杂度：O(n)，哈希表存储n个前缀和
记忆化递归法
使用记忆化技术缓存计算结果，为每个节点存储从该节点向下的路径和计数,优化递归效率。
import java.util.HashMap;
public class Solution {
public int pathSum(TreeNode root, int targetSum) {
return pathSumHelper(root, targetSum, new HashMap<>());
}
private int pathSumHelper(TreeNode node, int targetSum,
HashMap<TreeNode, Integer> memo) {
if (node == null) return 0;
// 如果结果已缓存，直接返回
if (memo.containsKey(node)) {
return memo.get(node);
}
// 计算以当前节点为起点的路径数
int count = countFromNode(node, targetSum, 0);
// 递归计算左右子树
count += pathSumHelper(node.left, targetSum, memo);
count += pathSumHelper(node.right, targetSum, memo);
// 缓存结果
memo.put(node, count);
return count;
}
private int countFromNode(TreeNode node, int targetSum, long currentSum) {
if (node == null) return 0;
currentSum += node.val;
int count = 0;
if (currentSum == targetSum) {
count++;
}
count += countFromNode(node.left, targetSum, currentSum);
count += countFromNode(node.right, targetSum, currentSum);
return count;
}
}
[*]时间复杂度：O(n)，每个节点计算一次
[*]空间复杂度：O(n)，缓存所有节点结果
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 前排留名，哈哈哈 新版吗？好像是停更了吧。 收藏一下 不知道什么时候能用到
页:
[1]