剑指offer-80、⼆叉树中和为某⼀值的路径(二)

题⽬描述

给定⼀个⼆叉树root和⼀个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。

• 该题路径定义不需要从根节点开始，也不需要在叶⼦节点结束，但是⼀定是从⽗亲节点往下到孩⼦节点
  
• 总节点数⽬为 n
  
• 保证最后返回的路径个数在整形范围内
  

假如⼆叉树 root 为 {1,2,3,4,5,4,3,#,#,-1} ， sum=6 ，那么总共如下所示，

思路及解答

双重递归法（暴力解法）

外层递归遍历所有节点作为起点，内层递归计算从该点向下的路径和

1. public class Solution {
2.     public int pathSum(TreeNode root, int targetSum) {
3.         if (root == null) return 0;
4.         
5.         // 以当前节点为起点的路径数 + 左右子树的路径数
6.         return countPaths(root, targetSum) +
7.                pathSum(root.left, targetSum) +
8.                pathSum(root.right, targetSum);
9.     }
10.    
11.     /**
12.      * 计算以当前节点为起点的路径数
13.      */
14.     private int countPaths(TreeNode node, long targetSum) {
15.         if (node == null) return 0;
16.         
17.         int count = 0;
18.         
19.         // 如果当前节点值等于目标值，找到一条路径
20.         if (node.val == targetSum) {
21.             count++;
22.         }
23.         
24.         // 递归计算左右子树
25.         count += countPaths(node.left, targetSum - node.val);
26.         count += countPaths(node.right, targetSum - node.val);
27.         
28.         return count;
29.     }
30. }

复制代码

• 时间复杂度：O(n²)，最坏情况下每个节点都要递归遍历其子树
  
• 空间复杂度：O(n)，递归栈深度
  

前缀和哈希表（最优解）

从根节点到当前节点的路径和curSum，查找curSum-targetSum是否存在
前缀和核心思想：

• 路径和 = 当前前缀和 - 之前某个前缀和
  
• curSum - targetSum是否存在于前缀和哈希表中
  
• 如果存在，说明从那个节点到当前节点的路径和为targetSum
  

执行示例（树[10,5,-3,3,2,null,11,3,-2,null,1]，sum=8）：

1. 从根到节点3：前缀和=10+5+3=18
2. targetSum=8 → 查找18-8=10是否存在
3. 哈希表中有10（根节点）→ 找到路径：5->3

复制代码

1. import java.util.HashMap;
3. public class Solution {
4.     public int pathSum(TreeNode root, int targetSum) {
5.         // 哈希表存储前缀和及其出现次数
6.         HashMap<Long, Integer> prefixSum = new HashMap<>();
7.         prefixSum.put(0L, 1); // 初始前缀和为0，出现1次
8.         
9.         return dfs(root, 0, targetSum, prefixSum);
10.     }
11.    
12.     private int dfs(TreeNode node, long curSum, int targetSum,
13.                     HashMap<Long, Integer> prefixSum) {
14.         if (node == null) return 0;
15.         
16.         // 计算从根节点到当前节点的前缀和
17.         curSum += node.val;
18.         
19.         // 查找前缀和中是否存在curSum - targetSum
20.         // 如果存在，说明从那个节点到当前节点的路径和为targetSum
21.         int count = prefixSum.getOrDefault(curSum - targetSum, 0);
22.         
23.         // 将当前前缀和加入哈希表
24.         prefixSum.put(curSum, prefixSum.getOrDefault(curSum, 0) + 1);
25.         
26.         // 递归处理左右子树
27.         count += dfs(node.left, curSum, targetSum, prefixSum);
28.         count += dfs(node.right, curSum, targetSum, prefixSum);
29.         
30.         // 回溯：移除当前前缀和，避免影响其他分支
31.         prefixSum.put(curSum, prefixSum.get(curSum) - 1);
32.         
33.         return count;
34.     }
35. }

复制代码

• 时间复杂度：O(n)，每个节点只访问一次
  
• 空间复杂度：O(n)，哈希表存储n个前缀和
  

记忆化递归法

使用记忆化技术缓存计算结果，为每个节点存储从该节点向下的路径和计数,优化递归效率。

1. import java.util.HashMap;
3. public class Solution {
4.     public int pathSum(TreeNode root, int targetSum) {
5.         return pathSumHelper(root, targetSum, new HashMap<>());
6.     }
7.    
8.     private int pathSumHelper(TreeNode node, int targetSum,
9.                               HashMap<TreeNode, Integer> memo) {
10.         if (node == null) return 0;
11.         
12.         // 如果结果已缓存，直接返回
13.         if (memo.containsKey(node)) {
14.             return memo.get(node);
15.         }
16.         
17.         // 计算以当前节点为起点的路径数
18.         int count = countFromNode(node, targetSum, 0);
19.         
20.         // 递归计算左右子树
21.         count += pathSumHelper(node.left, targetSum, memo);
22.         count += pathSumHelper(node.right, targetSum, memo);
23.         
24.         // 缓存结果
25.         memo.put(node, count);
26.         
27.         return count;
28.     }
29.    
30.     private int countFromNode(TreeNode node, int targetSum, long currentSum) {
31.         if (node == null) return 0;
32.         
33.         currentSum += node.val;
34.         int count = 0;
35.         
36.         if (currentSum == targetSum) {
37.             count++;
38.         }
39.         
40.         count += countFromNode(node.left, targetSum, currentSum);
41.         count += countFromNode(node.right, targetSum, currentSum);
42.         
43.         return count;
44.     }
45. }

复制代码

• 时间复杂度：O(n)，每个节点计算一次
  
• 空间复杂度：O(n)，缓存所有节点结果
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！