LeetCode 热题 100 437. 路径总和 III-EW帮帮网

LeetCode 热题 100 | 437. 路径总和 III

大家好，今天我们来解决一道经典的二叉树问题——路径总和 III。这道题在 LeetCode 上被标记为中等难度，要求计算二叉树中节点值之和等于给定目标值 targetSum 的路径数目。

问题描述

给定一个二叉树的根节点 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

解题思路

核心思想

前缀和：
- 使用前缀和的思想，记录从根节点到当前节点的路径和。
- 使用一个哈希表 prefix_sum_count 来记录前缀和出现的次数。
递归遍历：
- 递归遍历二叉树，对于每个节点，计算从根节点到当前节点的路径和。
- 检查是否存在一个前缀和，使得当前路径和减去目标值 targetSum 等于该前缀和，如果存在，则路径数目加一。
更新前缀和：
- 在递归过程中，更新前缀和的计数。
- 递归返回时，恢复前缀和的计数，确保不影响其他路径的计算。

Python代码实现

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        from collections import defaultdict
        
        def dfs(node, current_sum):
            nonlocal count
            if not node:
                return
            
            current_sum += node.val
            if current_sum - targetSum in prefix_sum_count:
                count += prefix_sum_count[current_sum - targetSum]
            
            prefix_sum_count[current_sum] += 1
            
            dfs(node.left, current_sum)
            dfs(node.right, current_sum)
            
            prefix_sum_count[current_sum] -= 1
        
        prefix_sum_count = defaultdict(int)
        prefix_sum_count[0] = 1
        count = 0
        dfs(root, 0)
        return count

代码解析

初始化：
- 使用 defaultdict 初始化前缀和计数器 prefix_sum_count，并设置初始值 prefix_sum_count[0] = 1。
- 初始化路径数目 count 为 0。
递归函数：
- 定义递归函数 dfs，用于遍历二叉树并计算路径和。
- 对于每个节点，更新当前路径和 current_sum。
- 检查是否存在一个前缀和，使得当前路径和减去目标值 targetSum 等于该前缀和，如果存在，则路径数目加一。
- 更新前缀和的计数。
- 递归调用 dfs，分别处理左子树和右子树。
- 递归返回时，恢复前缀和的计数。
主函数：
- 调用 dfs(root, 0)，从根节点开始遍历。
- 返回路径数目 count。

复杂度分析

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点被访问一次。
空间复杂度：O(n)，哈希表 prefix_sum_count 的大小最多为 n，递归调用栈的深度最多为树的高度。

示例运行

示例 1

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3

示例 2

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

总结

通过前缀和的思想，我们可以高效地计算二叉树中节点值之和等于目标值的路径数目。递归遍历二叉树，使用哈希表记录前缀和的出现次数，从而快速判断是否存在满足条件的路径。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！

LeetCode 热题 100 437. 路径总和 III