437. Path Sum III

Python

Preorder with Prefix Sum

from collections import defaultdict


class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        answer = 0
        prefix = defaultdict(int)

        def dfs(node, total):
            if not node:
                return

            nonlocal answer

            total += node.val
            if total == targetSum:
                answer += 1

            answer += prefix[total-targetSum]
            prefix[total] += 1

            dfs(node.left, total)
            dfs(node.right, total)

            prefix[total] -= 1

        dfs(root, 0)

        return answer