LeetCode--HOT100题（48）

题目描述：437. 路径总和 III（中等）

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

LeetCode做题链接：LeetCode-路径总和 III

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
1
2
3

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
1
2

提示：

二叉树的节点个数的范围是 [0,1000]
-109 <= Node.val <= 109 
-1000 <= targetSum <= 1000 
1
2
3

题目接口

/**
 * Definition for a binary tree node.
 * public 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 {
    public int pathSum(TreeNode root, int targetSum) {

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

解题思路

主要思路：

1. 定义一个哈希表preSumMap，用于存储前缀和及其出现次数。同时，将目标和target初始化为给定的目标和。
2. 调用递归函数recur来计算从根节点到叶子节点的路径和等于目标和的路径数量。
3. 在递归函数中，首先判断当前节点是否为空，如果为空则返回0，表示没有符合条件的路径。
4. 计算当前路径和curNum，即当前节点的值与前缀和的和。
5. 使用哈希表preSumMap查询curNum-target的前缀和出现的次数，如果不存在则默认为0。将结果存入res变量中。
6. 更新哈希表preSumMap，将curNum的出现次数加1。
7. 递归调用左子树和右子树，分别传入curNum作为新的前缀和，并将返回的结果累加到res中。
8. 回溯时，将哈希表preSumMap中curNum的出现次数减1，以便后续其他路径使用。
9. 返回res，即符合条件的路径数量。

通过递归地遍历二叉树的每个节点，并利用前缀和和哈希表进行动态规划，可以在O(N)的时间复杂度内求解路径和问题，其中N是二叉树的节点数。

代码

/**
 * Definition for a binary tree node.
 * public 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 {
    // 用于存储前缀和及其出现次数的哈希表
    Map<Long, Long> preSumMap;
    // 目标和
    Long target;

    public int pathSum(TreeNode root, int targetSum){
        preSumMap = new HashMap<>();
        target = Long.valueOf(targetSum);
        preSumMap.put(0L, 1L);

        return recur(root, 0L).intValue();
    }

    // 递归函数，计算从根节点到叶子节点的路径和等于目标和的路径数量
    private Long recur(TreeNode root, Long preSum){   //返回以root为根节点的符合题目条件的答案个数
        if(root == null) return 0L;
        Long curNum = Long.valueOf(root.val + preSum); //当前路径和
        Long res = preSumMap.getOrDefault(Long.valueOf(curNum-target), 0L); //更新答案
        preSumMap.put(Long.valueOf(curNum), preSumMap.getOrDefault(curNum, 0L)+1); //更新前缀和出现的次数

        res += recur(root.left, curNum);        //递归左子树
        res += recur(root.right, curNum);        //递归右子树

        preSumMap.put(Long.valueOf(curNum), preSumMap.get(curNum)-1); //回溯时，将当前前缀和的出现次数减1
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

成功！

PS:

感谢您的阅读！如果您觉得本篇文章对您有所帮助，请给予博主一个赞喔~