路径总和 III

本文介绍了 LeetCode 437 路径总和 III 的两种解法：双重递归和前缀和优化，并附有详细思路和 Python 代码。

Leetcode Python 二叉树前缀和递归

题目

437. 路径总和 III - 力扣（LeetCode）

解法一

思路

通过两个递归，将问题转化为：

对以每个节点作为起点的并且满足条件的路径有多少条？
递归遍历每个节点，求出总数

答案

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        if not root:
            return 0
        def dfs(node, target):
            if not node:
                return 0
            res = 0
            if target == node.val:
                res += 1
            res += dfs(node.left, target-node.val)
            res += dfs(node.right, target-node.val)
            return res
        res = dfs(root, targetSum)
        res += self.pathSum(root.left, targetSum)
        res += self.pathSum(root.right, targetSum)
        return res

解法二

利用前缀和的思想：若 A 点到 B 点的和为 X，则 B 点的前缀和 - A 点的前缀和 = X，即 A 点前缀和 = B 点前缀和 - X。

在本解法中，使用字典来记录存在某一个前缀和的节点的数量，key 为前缀和，value 为该前缀和对应的节点有多少个。

到了某一个新的节点，想查找是否存在满足条件的路径，则可用该字典查询是否存在前缀和 = 该点前缀和 - X的节点，存在的话有几个。

答案

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        mp = collections.defaultdict(int)
        mp[0] = 1
 
        # cur代表node节点之前的前缀和
        def dfs(node, cur):
            if not node:
                return 0
            cur += node.val
            # res代表前缀和为cur-targetSum的节点有没有，有几个？有的话就代表从该节点到node之间的路径和为targetSum
            res = mp[cur - targetSum]
            # 记得更新mp
            mp[cur] += 1
            res += dfs(node.left, cur)
            res += dfs(node.right, cur)
            # 记得恢复mp，不然从子节点到父节点也会被算进去
            mp[cur] -= 1
            return res
        
        return dfs(root, 0)