↓Skip to main content
  1. Posts/

LeetCode-437 路径总和 III

·1 min·
Table of Contents

LeetCode-437 路径总和 III #

Solution 1 #

前缀和 + 哈希表. 统计到每个节点时出现过的路径和.

代码如下:

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        ans = 0
        book = defaultdict(int)
        book[0] = 1
        def f(root, s):
            if root is None:
                return 
            s += root.val
            nonlocal ans
            ans += book[s - targetSum]
            book[s] += 1
            f(root.left, s)
            f(root.right, s)
            book[s] -= 1
        f(root, 0)
        return ans

Solution 2 #

递归.

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        if root is None:
            return 0

        def f(node, current_sum):
            if node is None:
                return 0
            current_sum += node.val
            res = 1 if current_sum == targetSum else 0
            res += f(node.left, current_sum)
            res += f(node.right, current_sum)
            return res

        return f(root, 0) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)