vvrf / DSA.log

问题拆解

统计二叉树中节点值之和等于 targetSum 的路径条数。路径不必从根出发、也不必到叶子结束，但方向必须向下（父到子）。

朴素做法是双重递归：外层遍历每个节点，内层以该节点为起点向下找和为 targetSum 的路径，时间 O(n²)。浪费在哪里？从根走到某个深处节点的路上，同一段和被反复累加。这和数组里“和为 k 的子数组”是同一个问题——数组上我们用前缀和加哈希表把它降到 O(n)，树上照搬即可：任何一条向下的路径都落在某条根到节点的链上，路径和等于两个前缀和之差。设当前根到节点的前缀和为 cur，那么以当前节点为终点、和为 targetSum 的路径条数，就是祖先链上前缀和等于 cur - targetSum 的节点个数。

树相对数组只多了一件事：哈希表里只能保留“当前节点到根”这条链上的前缀和，离开一个子树时必须把它的计数撤销掉。

前缀和哈希表 + 回溯撤销

用哈希表记录“从根到当前路径上，每个前缀和出现的次数”，DFS 进入节点时累加计数、查表统计，递归完左右子树后把自己的前缀和计数减回去。初始要放入 {0: 1}，代表空前缀，否则从根开始恰好等于 targetSum 的路径会被漏掉。

public int pathSum(TreeNode root, int targetSum) {
    Map<Long, Integer> prefix = new HashMap<>();
    prefix.put(0L, 1); // 空前缀，兜住从根开始的路径
    return dfs(root, 0L, targetSum, prefix);
}

private int dfs(TreeNode node, long cur, int target, Map<Long, Integer> prefix) {
    if (node == null) {
        return 0;
    }
    cur += node.val;
    int count = prefix.getOrDefault(cur - target, 0); // 以当前节点为终点的路径数
    prefix.merge(cur, 1, Integer::sum);
    count += dfs(node.left, cur, target, prefix);
    count += dfs(node.right, cur, target, prefix);
    prefix.merge(cur, -1, Integer::sum); // 离开子树，撤销自己的计数
    return count;
}

def pathSum(root: Optional[TreeNode], targetSum: int) -> int:
    prefix = defaultdict(int)
    prefix[0] = 1  # 空前缀，兜住从根开始的路径

    def dfs(node, cur):
        if not node:
            return 0
        cur += node.val
        count = prefix[cur - targetSum]  # 以当前节点为终点的路径数
        prefix[cur] += 1
        count += dfs(node.left, cur)
        count += dfs(node.right, cur)
        prefix[cur] -= 1  # 离开子树，撤销自己的计数
        return count

    return dfs(root, 0)

func pathSum(root *TreeNode, targetSum int) int {
    prefix := map[int]int{0: 1} // 空前缀，兜住从根开始的路径
    var dfs func(node *TreeNode, cur int) int
    dfs = func(node *TreeNode, cur int) int {
        if node == nil {
            return 0
        }
        cur += node.Val
        count := prefix[cur-targetSum] // 以当前节点为终点的路径数
        prefix[cur]++
        count += dfs(node.Left, cur)
        count += dfs(node.Right, cur)
        prefix[cur]-- // 离开子树，撤销自己的计数
        return count
    }
    return dfs(root, 0)
}

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> i32 {
    fn dfs(
        node: &Option<Rc<RefCell<TreeNode>>>,
        cur: i64,
        target: i64,
        prefix: &mut HashMap<i64, i32>,
    ) -> i32 {
        let Some(n) = node else {
            return 0;
        };
        let n = n.borrow();
        let cur = cur + n.val as i64;
        let mut count = *prefix.get(&(cur - target)).unwrap_or(&0); // 以当前节点为终点的路径数
        *prefix.entry(cur).or_insert(0) += 1;
        count += dfs(&n.left, cur, target, prefix);
        count += dfs(&n.right, cur, target, prefix);
        *prefix.entry(cur).or_insert(0) -= 1; // 离开子树，撤销自己的计数
        count
    }
    let mut prefix = HashMap::new();
    prefix.insert(0, 1); // 空前缀，兜住从根开始的路径
    dfs(&root, 0, target_sum as i64, &mut prefix)
}

最后一行的撤销是这题的核心细节。哈希表是整棵树共享的，但它任何时刻只应该反映“根到当前节点”这一条链：左子树里累出来的前缀和，对右子树的节点来说不是祖先，不能拿来配对。忘了撤销，两个分属不同分支的节点会被错误地拼成一条“路径”。另一个细节是查表和插入的顺序——先查 cur - target 再把 cur 放进表里，否则当 targetSum 为 0 时节点会跟自己配对。节点值和深度都可能很大，前缀和用 64 位整数更稳妥。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点进出各一次，哈希操作均摊 O(1)
空间	`O(n)`	哈希表最多存一条链的前缀和，加上递归栈深度

可以迁移的模式

“和为 k 的子数组”的前缀和哈希套路可以原样搬到树上，路径对应根链上两个前缀和之差；
共享的状态容器（哈希表、访问标记）在 DFS 回来时必须撤销修改，让它始终只描述当前路径——这就是回溯；
哈希表预置 {0: 1} 处理“从头开始恰好命中”的边界，数组和树上都少不了这一笔。

先查表、再登记、回来时注销，这三步的顺序在所有前缀和配对问题里都值得默念一遍。