路径总和 III：树上的前缀和

核心结论#

从根到当前节点的前缀和为 currentSum。如果祖先路径中出现过 currentSum - targetSum，从该祖先之后到当前节点的路径和就等于目标值。用哈希表记录当前递归路径上的前缀和次数，可以在线性时间内计数。

前缀和关系#

路径不必从根开始，但方向必须从父节点向子节点。假设祖先节点之前的前缀和是 previousSum：

currentSum - previousSum = targetSum
previousSum = currentSum - targetSum

前缀和可能超出 int 范围，因此累加值使用 long。

Java 实现#

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0L, 1);
        return countPaths(root, 0L, targetSum, prefixCounts);
    }

    private int countPaths(
        TreeNode node,
        long currentSum,
        int targetSum,
        Map<Long, Integer> prefixCounts
    ) {
        if (node == null) {
            return 0;
        }

        currentSum += node.val;
        int count = prefixCounts.getOrDefault(currentSum - targetSum, 0);
        prefixCounts.merge(currentSum, 1, Integer::sum);

        count += countPaths(node.left, currentSum, targetSum, prefixCounts);
        count += countPaths(node.right, currentSum, targetSum, prefixCounts);

        prefixCounts.merge(currentSum, -1, Integer::sum);
        return count;
    }
}

为什么需要回溯#

哈希表只能描述从根到当前节点的这一条路径。离开节点时必须撤销它的前缀和，否则左子树的状态会错误地参与右子树计数，形成并不存在的跨分支路径。

正确性与复杂度#

每个合法路径对应一对前缀和，其差为 targetSum；哈希表记录次数，因此重复前缀和也不会漏计。每个节点进入和退出各一次，平均时间复杂度为 O(n)，空间复杂度为 O(h) 到 O(n)。

验证#

覆盖空树、负数、零、重复前缀和、目标路径从根开始，以及目标路径位于非根子树的情况。

参考#

• LeetCode 437：路径总和 III