LeetCode 第 437 题：路径总和 III（Path Sum III）
字数 2195 2025-10-26 15:41:00

LeetCode 第 437 题：路径总和 III（Path Sum III）

题目描述
给定一个二叉树的根节点 root，和一个表示目标和的整数 targetSum。你需要找出二叉树中路径和等于 targetSum 的路径数目。这里的路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：存在三条路径，其路径和等于 8：

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

解题过程

第一步：理解问题核心
这个问题的关键在于路径的定义非常灵活：它可以从任意节点开始，到任意节点结束，只要路径是向下的即可。这不同于经典的“路径总和”问题（LeetCode 112题），那里要求从根到叶子节点。

第二步：初步思路——暴力DFS
最直观的想法是，我们可以遍历每个节点，并以每个节点作为路径的起点，向下搜索所有可能的路径，检查路径和是否等于 targetSum。

  1. 外层遍历：使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历二叉树中的每一个节点。
  2. 内层搜索：对于当前遍历到的节点，再启动一个DFS，计算从该节点出发，向下延伸的所有路径的和。每当路径和等于 targetSum 时，就将结果计数加1。

这种方法的时间复杂度是 O(N²)，在最坏情况下（链表形式的树）会达到 O(N²)。虽然思路简单，但对于较大的树可能效率不高。

第三步：引入优化思路——前缀和
为了优化，我们可以借鉴数组领域中“和为K的子数组”问题的思路，使用前缀和与哈希表来避免内层的重复计算。

  1. 前缀和概念迁移：在二叉树中，从根节点到当前节点的路径上的节点值之和，可以称为“前缀和”。
  2. 核心洞察：假设我们从根节点到当前节点 B 的前缀和是 currSum，而到路径上某个祖先节点 A 的前缀和是 prevSum。那么，从节点 A 到节点 B 的路径和就是 currSum - prevSum。
    • 我们的目标是让这个差值等于 targetSum，即 currSum - prevSum = targetSum。
    • 转换一下，就是 prevSum = currSum - targetSum。
  3. 哈希表的作用：我们用一个哈希表（比如 prefixSumCount）来记录，在从根节点到当前节点的路径上，每一种前缀和出现的次数。
    • 在DFS遍历过程中，我们计算当前路径的 currSum。
    • 然后，我们查看哈希表中，键为 (currSum - targetSum) 的值是多少。这个值就代表了：有多少个祖先节点，它们的前缀和正好是 currSum - targetSum。以这些祖先节点的下一个节点为起点，以当前节点为终点的路径，其和正好就是 targetSum。我们将这个值加到总计数中。
    • 接着，我们将当前 currSum 的记录在哈希表中增加一次。
    • 重要：回溯。当递归遍历完当前节点的左右子树，返回到当前节点的父节点时，我们必须将当前 currSum 在哈希表中的计数减1（这被称为“回溯”）。因为当前节点路径已经探索完毕，不应该再影响其他分支（比如其兄弟节点）的路径计算。

第四步：算法步骤详解

  1. 初始化一个哈希表 prefixMap，预先存入 {0: 1}。这表示前缀和为0的路径（可以理解为“空路径”）出现了一次，这有助于处理从根节点开始的路径正好等于 targetSum 的情况。
  2. 定义一个递归函数 dfs(node, currSum)：
    a. 如果节点 node 为空，返回 0。
    b. 计算当前路径和：currSum = currSum + node.val。
    c. 计算满足条件的路径数量：count = prefixMap.get(currSum - targetSum, 0)。（get 方法表示如果键不存在则返回0）。
    d. 更新哈希表：prefixMap[currSum] = prefixMap.get(currSum, 0) + 1。
    e. 递归计算左子树和右子树能带来的路径数：count += dfs(node.left, currSum) + dfs(node.right, currSum)。
    f. 回溯：在返回上一层递归之前，执行 prefixMap[currSum] = prefixMap[currSum] - 1。如果值减为0，最好删除该键以避免干扰。
    g. 返回当前节点为根的子树上找到的总路径数 count。
  3. 主函数调用 dfs(root, 0) 并返回结果。

第五步：复杂度分析

  • 时间复杂度：O(N)。每个节点我们只访问一次，在哈希表上的操作是 O(1) 的。
  • 空间复杂度：O(N)。空间消耗主要来自递归调用栈的深度，在最坏情况下（树退化为链表）是 O(N)。哈希表所占空间也是 O(N)。

这个方法将时间复杂度从 O(N²) 优化到了 O(N)，是一种非常经典的“空间换时间”以及“前缀和”思想的应用。

LeetCode 第 437 题：路径总和 III（Path Sum III） 题目描述 给定一个二叉树的根节点 root ，和一个表示目标和的整数 targetSum 。你需要找出二叉树中路径和等于 targetSum 的路径数目。这里的路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 示例 输入：root = [ 10,5,-3,3,2,null,11,3,-2,null,1 ], targetSum = 8 输出：3 解释：存在三条路径，其路径和等于 8： 5 -> 3 5 -> 2 -> 1 -3 -> 11 解题过程 第一步：理解问题核心 这个问题的关键在于路径的定义非常灵活：它可以从任意节点开始，到任意节点结束，只要路径是向下的即可。这不同于经典的“路径总和”问题（LeetCode 112题），那里要求从根到叶子节点。 第二步：初步思路——暴力DFS 最直观的想法是，我们可以遍历每个节点，并以每个节点作为路径的起点，向下搜索所有可能的路径，检查路径和是否等于 targetSum 。 外层遍历 ：使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历二叉树中的每一个节点。 内层搜索 ：对于当前遍历到的节点，再启动一个DFS，计算从该节点出发，向下延伸的所有路径的和。每当路径和等于 targetSum 时，就将结果计数加1。 这种方法的时间复杂度是 O(N²)，在最坏情况下（链表形式的树）会达到 O(N²)。虽然思路简单，但对于较大的树可能效率不高。 第三步：引入优化思路——前缀和 为了优化，我们可以借鉴数组领域中“和为K的子数组”问题的思路，使用 前缀和 与 哈希表 来避免内层的重复计算。 前缀和概念迁移 ：在二叉树中，从根节点到当前节点的路径上的节点值之和，可以称为“前缀和”。 核心洞察 ：假设我们从根节点到当前节点 B 的前缀和是 currSum ，而到路径上某个祖先节点 A 的前缀和是 prevSum 。那么，从节点 A 到节点 B 的路径和就是 currSum - prevSum 。 我们的目标是让这个差值等于 targetSum ，即 currSum - prevSum = targetSum 。 转换一下，就是 prevSum = currSum - targetSum 。 哈希表的作用 ：我们用一个哈希表（比如 prefixSumCount ）来记录，在从根节点到当前节点的路径上， 每一种前缀和出现的次数 。 在DFS遍历过程中，我们计算当前路径的 currSum 。 然后，我们查看哈希表中，键为 (currSum - targetSum) 的值是多少。这个值就代表了：有多少个祖先节点，它们的前缀和正好是 currSum - targetSum 。以这些祖先节点的 下一个节点 为起点，以当前节点为终点的路径，其和正好就是 targetSum 。我们将这个值加到总计数中。 接着，我们将当前 currSum 的记录在哈希表中增加一次。 重要：回溯 。当递归遍历完当前节点的左右子树，返回到当前节点的父节点时，我们必须将当前 currSum 在哈希表中的计数减1（这被称为“回溯”）。因为当前节点路径已经探索完毕，不应该再影响其他分支（比如其兄弟节点）的路径计算。 第四步：算法步骤详解 初始化一个哈希表 prefixMap ，预先存入 {0: 1} 。这表示前缀和为0的路径（可以理解为“空路径”）出现了一次，这有助于处理从根节点开始的路径正好等于 targetSum 的情况。 定义一个递归函数 dfs(node, currSum) ： a. 如果节点 node 为空，返回 0。 b. 计算当前路径和： currSum = currSum + node.val 。 c. 计算满足条件的路径数量： count = prefixMap.get(currSum - targetSum, 0) 。（ get 方法表示如果键不存在则返回0）。 d. 更新哈希表： prefixMap[currSum] = prefixMap.get(currSum, 0) + 1 。 e. 递归计算左子树和右子树能带来的路径数： count += dfs(node.left, currSum) + dfs(node.right, currSum) 。 f. 回溯 ：在返回上一层递归之前，执行 prefixMap[currSum] = prefixMap[currSum] - 1 。如果值减为0，最好删除该键以避免干扰。 g. 返回当前节点为根的子树上找到的总路径数 count 。 主函数调用 dfs(root, 0) 并返回结果。 第五步：复杂度分析 时间复杂度 ：O(N)。每个节点我们只访问一次，在哈希表上的操作是 O(1) 的。 空间复杂度 ：O(N)。空间消耗主要来自递归调用栈的深度，在最坏情况下（树退化为链表）是 O(N)。哈希表所占空间也是 O(N)。 这个方法将时间复杂度从 O(N²) 优化到了 O(N)，是一种非常经典的“空间换时间”以及“前缀和”思想的应用。