[LeetCode] 437. 路径总和 III

首先，我们需要清楚地理解题目要求。给定一个二叉树，每个节点都有一个整数值。我们需要找出所有路径和等于给定数值的路径总数。这里的路径有以下几个特点：

1. 路径方向：路径必须是向下的，即只能从父节点到子节点，不能反向。
2. 路径起点和终点：路径不需要从根节点开始，也不需要在叶子节点结束。也就是说，路径可以在树中的任何节点开始和结束，只要满足方向向下。
3. 路径长度：路径至少包含一个节点。

给定的示例是：

需要找出所有和为8的路径。根据示例，正确的路径有：

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

让我们验证一下：

• 5 -> 3: 5 + 3 = 8
• 5 -> 2 -> 1: 5 + 2 + 1 = 8
• -3 -> 11: -3 + 11 = 8

确实有三条路径满足条件。

暴力法的思路是：

1. 对于树中的每一个节点，以该节点为起点，向下进行深度优先搜索（DFS），计算从该节点开始的所有路径的和，统计等于目标值的路径数量。
2. 对整棵树的每一个节点都执行上述操作，最后将所有统计的数量相加。

具体步骤：

• 使用一个外层DFS遍历树的每一个节点（dfs2）。
• 对于每一个节点，使用另一个内层DFS计算以该节点为起点的所有路径和（dfs1），并统计满足条件的路径。

代码实现：

解释：

• dfs1(root, _sum)：计算以root为起点的路径中，路径和等于_sum的数量。每次递归调用时，_sum减去当前节点的值，如果_sum减到0，说明找到一条满足条件的路径。
• dfs2(root)：遍历树的每一个节点，对每个节点调用dfs1，从该节点开始寻找路径。

复杂度分析：

• 时间复杂度：O(n^2)，其中n是树的节点数。对于每个节点，我们可能需要遍历其所有子节点。
• 空间复杂度：O(n)，递归栈的深度在最坏情况下是树的高度，对于平衡树是O(log n)，对于最坏情况（链表）是O(n)。

这种方法利用了前缀和的概念，类似于数组中的前缀和，但在树中进行。前缀和可以帮助我们快速计算从某个节点到当前节点的路径和。

前缀和定义：

从根节点到当前节点的路径上所有节点的和。

思路：

1. 使用一个哈希表（prefix）来记录从根节点到当前节点的路径中，各个前缀和出现的次数。
2. 初始化时，prefix[0] = 1，表示前缀和为0出现了一次（即根节点之前）。
3. 进行深度优先搜索（DFS），在遍历每个节点时：

   计算当前的前缀和cur。

   计算target = cur - _sum，即我们需要的前缀和，使得从某个祖先节点到当前节点的路径和为_sum。

   res += prefix[target]，即之前有多少前缀和等于target，就有多少条路径满足条件。

   更新prefix[cur]，表示当前前缀和的出现次数加一。

   递归处理左子树和右子树。

   回溯：在返回之前，将prefix[cur]减一，因为我们要回到上一层，当前的前缀和不再影响其他分支。

代码实现：

解释：

• prefix：哈希表，记录前缀和及其出现次数。
• dfs(root, cur)：

  cur：从根节点到当前节点的路径和。

  target = cur - _sum：如果之前存在前缀和等于target，那么从那个节点到当前节点的路径和就是_sum。

  res += prefix[target]：累加满足条件的路径数量。

  prefix[cur] += 1：记录当前前缀和。

  递归处理左右子树。

  prefix[cur] -= 1：回溯，恢复prefix的状态。

复杂度分析：

• 时间复杂度：O(n)，每个节点只被访问一次。
• 空间复杂度：O(n)，哈希表在最坏情况下存储n个不同的前缀和。

• 暴力法：

  优点：直观，易于理解。

  缺点：时间复杂度较高，对于大树效率较低。

• 前缀和 + 回溯：

  优点：时间复杂度低，效率高。

  缺点：需要理解前缀和的概念，实现稍复杂。

在实际应用中，如果树的规模不大（如题目中节点数不超过1000），暴力法也是可以接受的。但对于更大的树或需要高效处理的场景，前缀和的方法更为优越。

让我们用前缀和的方法验证示例：

初始：

• prefix = {0: 1}
• res = 0

遍历：

1. 根节点10：

   cur = 0 + 10 = 10

   target = 10 - 8 = 2

   prefix[2]不存在，res += 0

   prefix = {0:1, 10:1}

   递归左（5），右（-3）

2. 左子节点5：

   cur = 10 + 5 = 15

   target = 15 - 8 = 7

   prefix[7]不存在，res += 0

   prefix = {0:1, 10:1, 15:1}

   递归左（3），右（2）

3. 左子节点3：

   cur = 15 + 3 = 18

   target = 18 - 8 = 10

   prefix[10] = 1，res += 1（路径10->5->3，但实际是从5开始，所以这里需要调整理解）

   实际上，前缀和是从根开始的，所以target=10对应的是从根到某个点的和为10，然后从那个点到当前点的和为8。但这里我们是从5开始，所以可能需要重新思考。

   看起来这里的前缀和定义可能需要调整。更准确地说，前缀和是从当前节点到根的路径和的相反数（因为我们在计算cur时是从根累加下来的）。可能需要重新梳理。

   更准确的前缀和定义：

   我们定义prefix为从根到当前节点的路径和。

   当我们计算cur时，是从根到当前节点的和。

   我们需要找的是是否存在一个祖先节点，使得cur - ancestor_sum = _sum，即ancestor_sum = cur - _sum。

   因此，prefix应该记录从根到当前节点的路径和。

   可能在之前的解释中有些混淆。让我们重新定义：

   prefix记录从根到当前节点的路径和的出现次数。

   初始时，prefix = {0:1}，表示在根节点之前，前缀和为0（即没有节点时）。

   对于每个节点，计算从根到该节点的和cur。

   我们需要找的是prefix[cur - _sum]，即之前有多少路径的和为cur - _sum，这样从那个节点到当前节点的和就是_sum。

   然后将cur加入prefix，递归处理子节点，最后回溯（prefix[cur] -= 1）。

   这样，对于示例：

   初始prefix = {0:1}

   根10：

   cur = 10

   target = 10 - 8 = 2

   prefix[2]不存在，res += 0

   prefix = {0:1, 10:1}

   递归左5，右-3

   左5：

   cur = 10 + 5 = 15

   target = 15 - 8 = 7

   prefix[7]不存在，res += 0

   prefix = {0:1, 10:1, 15:1}

   递归左3，右2

   左3：

   cur = 15 + 3 = 18

   target = 18 - 8 = 10

   prefix[10] = 1，res += 1（路径5->3）

   prefix = {0:1, 10:1, 15:1, 18:1}

   递归左3，右-2

   左3：

   cur = 18 + 3 = 21

   target = 21 - 8 = 13

   prefix[13]不存在，res += 0

   prefix = {0:1, 10:1, 15:1, 18:1, 21:1}

   无左右子节点，返回

   prefix[21] -= 1（即删除，因为之前是1，减后为0）

   右-2：

   cur = 18 + (-2) = 16

   target = 16 - 8 = 8

   prefix[8]不存在，res += 0

   prefix = {0:1, 10:1, 15:1, 18:1, 16:1}

   无左右子节点，返回

   prefix[16] -= 1

   返回到5的右2：

   cur = 15 + 2 = 17

   target = 17 - 8 = 9

   prefix[9]不存在，res += 0

   prefix = {0:1, 10:1, 15:1, 18:1, 17:1}

   递归右1

   右1：

   cur = 17 + 1 = 18

   target = 18 - 8 = 10

   prefix[10] = 1，res += 1（路径5->2->1）

   prefix = {0:1, 10:1, 15:1, 18:2}（因为之前18已经存在）

   无左右子节点，返回

   prefix[18] -= 1（从2减到1）

   返回到10的右-3：

   cur = 10 + (-3) = 7

   target = 7 - 8 = -1

   prefix[-1]不存在，res += 0

   prefix = {0:1, 10:1, 15:1, 18:1, 7:1}

   递归右11

   右11：

   cur = 7 + 11 = 18

   target = 18 - 8 = 10

   prefix[10] = 1，res += 1（路径-3->11）

   prefix = {0:1, 10:1, 15:1, 18:2, 7:1}

   无左右子节点，返回

   prefix[18] -= 1（从2减到1）

   最终res = 3，与示例一致。

在实现前缀和的方法时，容易犯的错误包括：

1. 前缀和的定义：容易混淆前缀和是从根到当前节点还是从当前节点到根。正确的定义是从根到当前节点的路径和。
2. 回溯的处理：在递归返回时，必须将当前前缀和的计数减一，否则会影响其他分支的计算。
3. 初始条件：prefix[0] = 1是必要的，表示在根节点之前的前缀和为0。

在Python中，可以使用defaultdict来简化哈希表的操作：

通过这道题目，我们学习了两种解决路径和问题的方法：

1. 暴力法：直观但效率较低，适合小规模数据。
2. 前缀和 + 回溯：高效，利用前缀和快速计算路径和，适合大规模数据。

在实际应用中，应根据数据规模选择合适的方法。对于LeetCode的这道题目，两种方法都可以通过，但前缀和的方法更为高效。