LC 437路径总和 IIIPath Sum III　中等

统计二叉树中节点值之和等于 target 的向下路径条数，路径不必从根开始。

思路 前缀和 + 哈希回溯：累加 cnt[当前前缀和 - target]，递归后撤销计数防跨子树。时间 O(n)。

class Solution:
    def pathSum(self, root, targetSum):
        def dfs(node, cur, cnt):
            if not node:
                return 0
            cur += node.val
            total = cnt[cur - targetSum]
            cnt[cur] += 1
            total += dfs(node.left, cur, cnt)
            total += dfs(node.right, cur, cnt)
            cnt[cur] -= 1
            return total
        return dfs(root, 0, defaultdict(int, {0: 1}))