二叉树路径和等于 targetSum 的路径数（路径可以不从根节点开始，方向必须向下）?

这是经典题（LeetCode 437：Path Sum III）：**统计二叉树中“向下路径”之和等于 `targetSum` 的条数**，路径可以从任意节点开始、到任意节点结束，但方向必须自上而下（从父到子）。 # 解法一：前缀和 + 哈希表（最优，O(n)） 思路跟数组前缀和一样，区别是在树上用 DFS 维护一条从根到当前节点的路径前缀和。 * 设 `preSum` 为当前从根到此节点的路径和，想找以**当前节点为结尾**的合法路径数量，就是统计**之前**出现过多少个前缀和为 `preSum - target`。 * 用 `Map<sum, freq>` 记录**到达当前节点前**各前缀和出现次数；进入节点时查询、累加答案，再将 `preSum` 计数 +1，递归左右子树；**回溯**时把 `preSum` 计数 -1，避免影响兄弟分支。 复杂度：每个节点只进出一次，**时间 O(n)**、空间平均 O(h)（栈）+ O(n)（哈希表最坏）。 ### Java 实现 ```java // Definition for a binary tree node. class TreeNode { int val; TreeNode left, right; TreeNode(int v) { val = v; } } public class Solution { public int pathSum(TreeNode root, int targetSum) { java.util.Map<Long, Integer> freq = new java.util.HashMap<>(); // 前缀和为 0 的路径出现 1 次（空路径基准） freq.put(0L, 1); return dfs(root, 0L, targetSum, freq); } private int dfs(TreeNode node, long preSum, int target, java.util.Map<Long, Integer> freq) { if (node == null) return 0; preSum += node.val; // 以当前节点为结尾、和为 target 的路径数 int ansHere = freq.getOrDefault(preSum - target, 0); // 当前前缀和入表 freq.put(preSum, freq.getOrDefault(preSum, 0) + 1); // 递归左右子树 int ans = ansHere + dfs(node.left, preSum, target, freq) + dfs(node.right, preSum, target, freq); // 回溯：移除当前前缀和 int cnt = freq.get(preSum) - 1; if (cnt == 0) freq.remove(preSum); else freq.put(preSum, cnt); return ans; } } ``` **实现细节与坑：** * 用 `long preSum` 防止节点值/路径和溢出 `int`。 * `freq.put(0L, 1)` 是关键：允许从任意节点开始的路径（等价于“从根到当前的前缀和本身就等于 target”）。 * 回溯时一定要把计数减回去，否则会“串味”到兄弟子树。 # 解法二：枚举起点的双层 DFS（直观，O(n²) 最坏） 对每个节点都以它作为起点向下 DFS 累加并统计。 最坏退化为链表时 O(n²)，实现简单但在大树/退化树上性能差。 ```java public int pathSum_bruteforce(TreeNode root, int target) { if (root == null) return 0; return countFrom(root, target) + pathSum_bruteforce(root.left, target) + pathSum_bruteforce(root.right, target); } private int countFrom(TreeNode node, long remain) { if (node == null) return 0; int ans = (node.val == remain) ? 1 : 0; return ans + countFrom(node.left, remain - node.val) + countFrom(node.right, remain - node.val); } ``` # 小结（面试速答） * **要求**：路径向下、可从任意节点开始；统计条数。 * **最优解**：树上前缀和 + 哈希表，**O(n)**；进入节点查 `preSum - target`，回溯时撤销前缀和计数。 * **边界**：节点值可负、路径和可能溢出 → 用 `long`；记得初始化 `freq(0)=1` 与回溯减计数。