路径总和 III 图解题解

这道题的路径和普通路径有什么不同

题目求树中和等于 targetSum 的路径条数，但这里的路径被重新定义了：方向只能向下（父到子）、必须连续，起点和终点却都任意——不必从根出发，也不必到叶子结束。另外节点值可以是负数，这意味着「和已经超了就提前剪枝」之类的想法不成立，也让同一条链上可能出现多段和相同的情况。

为什么暴力枚举起点是 O(n²)

直觉做法是双重递归：外层枚举每个节点作为路径起点，内层从这个起点向下累加、每凑够一次 targetSum 就计一条。每个节点会被它的所有祖先各扫一遍，链状树时总工作量是 1 加到 n，时间 O(n²)。慢的根源是重复累加：从根到某个深处节点的这段和，被沿途每个起点反反复复地重新算。

前缀和为什么能把树上路径变成一次查表

把「根到节点 X 的累加和」叫作 X 的前缀和 prefix(X)。同一条根链上，从祖先 A 的下一个节点走到当前节点 cur 的这段路径，和恰好等于 prefix(cur) - prefix(A)——两段根链相减，公共部分抵消。想让这段和等于 targetSum，等价于在 cur 的祖先里找前缀和等于 prefix(cur) - targetSum 的位置。

于是「向下枚举所有起点」被翻转成「向上数一次祖先」：用哈希表记录当前根链上每个前缀和出现的次数，走到 cur 时查一下 prefix - targetSum 出现过几次，就是以 cur 结尾的合法路径数。这正是数组版两数之和的查表思想，原封不动搬到了树的根链上。

哈希表为什么要预置 0 出现 1 次，回溯为什么必须撤销

表里要先放一条「前缀和 0 出现 1 次」，代表空前缀：当 prefix(cur) 本身就等于 targetSum 时，要找的是前缀和为 0 的祖先——对应从根一路走到 cur 的整段路径，不预置就会漏数这一整类。

更关键的是回溯撤销：递归离开一个节点时，必须把它的前缀和从表里减掉。因为差值公式只对同一条根链上的祖先成立，若左子树登记的前缀和残留在表里，右子树查表时会把跨分支的组合误当成路径，而题目要求路径必须连续。哈希表在任意时刻只保存根到当前节点这条链上的前缀和——这就是算法全程维持的不变量。

复杂度怎么算，容易错在哪

每个节点访问一次，查表、登记、撤销都是 O(1)，总时间 O(n)；哈希表加递归栈的空间是 O(n)。相比 O(n²) 的暴力，树一大差距悬殊。

三个高频坑：忘了预置空前缀，从根开始的路径全部漏掉；递归返回时不撤销登记，跨分支误判多算；以及哈希的值要存出现次数而不是存在与否——节点有负数时，同一个前缀和可能在一条链上出现多次，每一次都对应一条不同的路径。

Java

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> cnt = new HashMap<>();
        cnt.put(0L, 1);                 // 基底：空前缀出现 1 次
        return dfs(root, 0L, targetSum, cnt);
    }
    private int dfs(TreeNode node, long prefix, int target,
                    Map<Long, Integer> cnt) {
        if (node == null) return 0;
        prefix += node.val;             // 根到当前的前缀和
        int paths = cnt.getOrDefault(prefix - target, 0); // 命中=合法路径
        cnt.merge(prefix, 1, Integer::sum);               // 记入当前前缀
        paths += dfs(node.left,  prefix, target, cnt);
        paths += dfs(node.right, prefix, target, cnt);
        cnt.merge(prefix, -1, Integer::sum);              // 回溯撤销
        return paths;
    }
}

Python

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        from collections import defaultdict
        cnt = defaultdict(int)
        cnt[0] = 1                       # 基底：空前缀
        def dfs(node, prefix):
            if not node:
                return 0
            prefix += node.val            # 根到当前前缀和
            paths = cnt[prefix - target]  # 命中=合法路径数
            cnt[prefix] += 1              # 记入当前前缀
            paths += dfs(node.left,  prefix)
            paths += dfs(node.right, prefix)
            cnt[prefix] -= 1              # 回溯撤销
            return paths
        target = targetSum
        return dfs(root, 0)

C++

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        unordered_map<long, int> cnt;
        cnt[0] = 1;                        // 基底：空前缀
        return dfs(root, 0L, targetSum, cnt);
    }
    int dfs(TreeNode* node, long prefix, int target,
            unordered_map<long, int>& cnt) {
        if (!node) return 0;
        prefix += node->val;               // 根到当前前缀和
        int paths = cnt.count(prefix - target) ? cnt[prefix - target] : 0;
        cnt[prefix]++;                     // 记入当前前缀
        paths += dfs(node->left,  prefix, target, cnt);
        paths += dfs(node->right, prefix, target, cnt);
        cnt[prefix]--;                     // 回溯撤销
        return paths;
    }
};