437_路径总和 III[MEDIUM]
约 402 字大约 1 分钟
2026-03-13
题目:path-sum-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解题思路
- 前序遍历二叉树,用 前缀和 统计
当前和-目标和(currSum - targetSum) 在不在缓存里? - 注意递归完一个子树,就从缓存里扣除当前的 currSum ,因为从左子树换到右子树了,不再满足路径方向必须向下的前提
Java 实现
class Solution {
// key: 前缀和 value: 该前缀和出现的次数
Map<Long, Integer> map = new HashMap<>();
private int count;
public int pathSum(TreeNode root, int targetSum) {
if (root == null){
return 0;
}
count = 0;
map.put(0L,1);
preOrder(root, targetSum, 0L);
return count;
}
private void preOrder(TreeNode root, int targetSum, long currSum){
if (root == null){
return ;
}
currSum += root.val;
if (map.containsKey(currSum - targetSum)){
count += map.get(currSum - targetSum);
}
// 该前缀和是否已经存在 map 中,如果不在,则为 1,否则 +1
map.compute(currSum, (key, value) -> value == null ? 1 : value + 1);
preOrder(root.left, targetSum, currSum);
preOrder(root.right, targetSum, currSum);
// 递归完一个子树,就从缓存里扣除当前的 currSum
map.compute(currSum, (key, value) -> value == null ? 0 : value - 1);
}
}