剑指offer-80、⼆叉树中和为某⼀值的路径(二)
<h2 id="题描述">题⽬描述</h2><p>给定⼀个⼆叉树root和⼀个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。</p>
<ol>
<li>该题路径定义不需要从根节点开始，也不需要在叶⼦节点结束，但是⼀定是从⽗亲节点往下到孩⼦节点</li>
<li>总节点数⽬为 n</li>
<li>保证最后返回的路径个数在整形范围内</li>
</ol>
<p>假如⼆叉树 root 为 {1,2,3,4,5,4,3,#,#,-1} ， sum=6 ，那么总共如下所示，</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202505251146836.png" alt="" loading="lazy"></p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="双重递归法暴力解法">双重递归法（暴力解法）</h3>
<p>外层递归遍历所有节点作为起点，内层递归计算从该点向下的路径和</p>
<pre><code class="language-java">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;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，最坏情况下每个节点都要递归遍历其子树</li>
<li><strong>空间复杂度</strong>：O(n)，递归栈深度</li>
</ul>
<h3 id="前缀和哈希表最优解">前缀和哈希表（最优解）</h3>
<p>从根节点到当前节点的路径和curSum，查找curSum-targetSum是否存在</p>
<p>前缀和<strong>核心思想：</strong></p>
<ul>
<li>路径和 = 当前前缀和 - 之前某个前缀和</li>
<li><code>curSum - targetSum</code>是否存在于前缀和哈希表中</li>
<li>如果存在，说明从那个节点到当前节点的路径和为targetSum</li>
</ul>
<p><strong>执行示例（树，sum=8）：</strong></p>
<pre><code class="language-text">从根到节点3：前缀和=10+5+3=18
targetSum=8 → 查找18-8=10是否存在
哈希表中有10（根节点）→ 找到路径：5->3
</code></pre>
<pre><code class="language-java">import 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;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个节点只访问一次</li>
<li><strong>空间复杂度</strong>：O(n)，哈希表存储n个前缀和</li>
</ul>
<h3 id="记忆化递归法">记忆化递归法</h3>
<p>使用记忆化技术缓存计算结果，为每个节点存储从该节点向下的路径和计数,优化递归效率。</p>
<pre><code class="language-java">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;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，每个节点计算一次</li>
<li><strong>空间复杂度</strong>：O(n)，缓存所有节点结果</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19648887
頁:
[1]