更新时间：2025-03-31
- 算法题解目录汇总：算法刷题记录——题解目录汇总
- 技术博客总目录：计算机技术系列博客——目录页
优先整理热门100及面试150，不定期持续更新，欢迎关注！
437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示:
二叉树的节点个数的范围是 [0,1000]-10^9 <= Node.val <= 10^9-1000 <= targetSum <= 1000
方法一：前缀和+哈希表
利用前缀和和哈希表来高效统计路径数目。遍历树时维护从根到当前节点的前缀和，通过哈希表快速查找是否存在所需的前缀和差，从而统计符合条件的路径数目。
- 初始化哈希表：记录前缀和及其出现次数，初始时前缀和0出现一次，处理从根开始的路径。
- 深度优先搜索：递归遍历每个节点，计算当前前缀和，并检查哈希表中是否存在
currentSum - targetSum，存在则累加次数。 - 更新与回溯：在递归子节点前更新哈希表，递归完成后回溯，恢复哈希表状态，避免不同分支干扰。
代码实现(Java)：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class Solution {
private int count = 0;
private int target;
private Map<Long, Integer> prefixMap = new HashMap<>();
public int pathSum(TreeNode root, int targetSum) {
target = targetSum;
prefixMap.put(0L, 1); // 初始前缀和为0出现一次
dfs(root, 0L);
return count;
}
private void dfs(TreeNode node, long currentSum) {
if (node == null) {
return;
}
currentSum += node.val; // 更新当前前缀和
// 查找是否存在所需的前缀差
long required = currentSum - target;
count += prefixMap.getOrDefault(required, 0);
// 将当前前缀和加入哈希表
prefixMap.put(currentSum, prefixMap.getOrDefault(currentSum, 0) + 1);
// 递归处理子节点
dfs(node.left, currentSum);
dfs(node.right, currentSum);
// 回溯，移除当前前缀和
prefixMap.put(currentSum, prefixMap.get(currentSum) - 1);
if (prefixMap.get(currentSum) == 0) {
prefixMap.remove(currentSum);
}
}
}
方法一复杂度分析：
- 时间复杂度：
O(n)，每个节点访问一次，哈希表操作均摊O(1)。 - 空间复杂度：
O(n)，哈希表存储前缀和的数量最多为树的高度，最坏情况下为O(n)。
方法二：双重递归
遍历每个节点作为路径起点，递归计算以该节点为起点的所有路径和。
代码实现(Java)：
class Solution {
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
// 当前节点作为起点的路径数 + 左子树所有节点的路径数 + 右子树所有节点的路径数
return countPath(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
}
// 计算以node为起点的路径和等于target的数目
private int countPath(TreeNode node, long target) {
if (node == null) return 0;
int count = 0;
if (node.val == target) count++;
count += countPath(node.left, target - node.val);
count += countPath(node.right, target - node.val);
return count;
}
}
方法二复杂度分析：
- 时间复杂度：
O(n^2)，每个节点都会被访问一次，触发对左右子树的递归调用。 - 空间复杂度：
O(n)，由递归调用栈深度决定：最坏情况（退化为链表）递归深度为O(n)。
声明
- 本文版权归
CSDN用户Allen Wurlitzer所有，遵循CC-BY-SA协议发布，转载请注明出处。- 本文题目来源
力扣-LeetCode，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。