当前位置：首页 > news >正文

【LeetCode 热题 100】437. 路径总和 III——（解法一）递归递归！

news 2025/7/20 11:01:56

Problem: 437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(N^2) (最坏情况), O(N log N) (平均情况)
- 空间复杂度：O(H)，其中 H 是树的高度

整体思路

这段代码旨在解决一个经典的二叉树问题：路径总和 III (Path Sum III)。问题要求计算一棵二叉树中，节点值之和等于目标值 targetSum 的路径的数量。这里的“路径”必须是向下的（从父节点到子节点），但它不必从根节点开始，也不必在叶子节点结束。

该算法采用了一种 递归的“分治”思想。它巧妙地将问题分解为三个互不重叠的子问题，在树的每个节点上进行计算：

问题的分解：对于树中的任意一个节点 node，所有满足条件的路径可以被归为三类：
a. 路径 必须以 node 为起点。
b. 所有满足条件的路径 完全位于 node 的左子树 中（即路径的起点和终点都在左子树）。
c. 所有满足条件的路径 完全位于 node 的右子树 中。
双重递归结构：为了解决这个问题，代码使用了双重递归：
- 主递归函数 pathSum：这个函数是“分治”的实施者。对于当前节点 root，它的任务是计算上述三类路径的总和。
  - 它通过调用一个辅助函数 dfs(root, targetSum) 来计算第一类路径的数量。
  - 它通过递归调用 pathSum(root.left, targetSum) 来计算第二类路径的数量。
  - 它通过递归调用 pathSum(root.right, targetSum) 来计算第三类路径的数量。
  - 最后将这三者的结果相加，就是以 root 为根的树中所有满足条件的路径总数。
- 辅助递归函数 dfs：这个函数的目标很专一：计算必须以给定节点 node 为起点的路径中，和为 sum 的路径有多少条。
  - 它通过将 sum 减去当前节点的值，然后带着这个新的“剩余和”继续向其左右子节点递归。
  - 如果在任何一个节点上，“剩余和”恰好等于0，就意味着找到了一条满足条件的路径，计数器加一。

通过这种“主递归遍历每个节点作为潜在起点，辅助递归从该起点向下探索”的模式，算法可以不重不漏地找出所有符合条件的路径。

完整代码

class Solution {/*** 主函数：计算二叉树中路径和等于 targetSum 的路径数量。* @param root 树的根节点* @param targetSum 目标和* @return 满足条件的路径数量*/public int pathSum(TreeNode root, int targetSum) {// 递归的终止条件：如果当前节点为空，则不存在任何路径，返回0。if (root == null) {return 0;}// 分治思想的体现：问题分解为三个部分// 1. 计算以当前 root 节点为起点的路径数量。//    这个任务交由辅助函数 dfs 完成。int pathsFromRoot = dfs(root, targetSum);// 2. 递归地计算在左子树中，所有满足条件的路径数量。//    注意：这些路径的起点和终点都必须在左子树内部。int pathsOnLeft = pathSum(root.left, targetSum);// 3. 递归地计算在右子树中，所有满足条件的路径数量。int pathsOnRight = pathSum(root.right, targetSum);// 最终结果是这三个不相交的路径集合的数量之和。return pathsFromRoot + pathsOnLeft + pathsOnRight;   }/*** 辅助函数：计算以指定节点 node 为起点，路径和为 sum 的路径数量。* @param node 路径的起始节点* @param sum 目标和（在递归过程中表示剩余需要达成的和）* @return 从 node 出发的满足条件的路径数量*/private int dfs(TreeNode node, long sum) {// 递归的终止条件：如果节点为空，说明此路不通，返回0。if (node == null) {return 0;}// 计算包含当前节点后，还需要多少和才能达到目标。// 使用 long 类型是为了防止节点值累加后发生整数溢出。long remainSum = sum - node.val;// 检查当前路径是否正好满足条件。// 如果 remainSum 为 0，说明从起点到当前节点的路径和恰好等于目标和。int cnt = (remainSum == 0) ? 1 : 0;// 继续向下探索：// 递归地在左子树中寻找以 node.left 为延续的路径。cnt += dfs(node.left, remainSum);// 递归地在右子树中寻找以 node.right 为延续的路径。cnt += dfs(node.right, remainSum);// 返回从 node 出发找到的路径总数。return cnt;}
}

时空复杂度

时间复杂度：O(N^2) (最坏情况), O(N log N) (平均情况)

分析结构：pathSum 函数会对树中的每个节点调用一次。假设树有 N 个节点。在 pathSum(node) 的每次调用中，它都会启动一次 dfs(node, ...)。
dfs 的开销：dfs(node, ...) 会遍历以 node 为根的整个子树。如果这个子树有 k 个节点，那么 dfs 的时间复杂度就是 O(k)。
总开销：因此，总的时间复杂度可以看作是树中每个节点 u 都作为起点进行了一次深度优先搜索，搜索范围是 u 的子树。
- 总时间 = Σ (对每个节点 u) O(size_of_subtree(u))
最坏情况（Skewed Tree，链状树）：
- 如果树退化成一个链表，节点数为 N。
- pathSum 对根节点调用 dfs，耗时 O(N)。
- 对第二个节点调用 dfs，耗时 O(N-1)。
- …
- 总时间复杂度为 O(N + (N-1) + … + 1) = O(N^2)。
平均情况（Balanced Tree，平衡二叉树）：
- 对于一棵平衡二叉树，一个节点的子树大小与其深度有关。
- 每个节点 u 被访问的次数等于其在树中的深度 depth(u)。总的访问次数可以看作是 Σ depth(u)，这大致等于 N * log N。
- 因此，在树比较平衡的情况下，时间复杂度为 O(N log N)。

空间复杂度：O(H)，其中 H 是树的高度

递归调用栈：该算法的空间复杂度主要由递归调用的深度决定。
pathSum 和 dfs 的关系：pathSum 的递归深度和 dfs 的递归深度不会简单相加，因为它们是嵌套调用的。在任一时刻，调用栈的最大深度受限于树的高度 H。
最坏情况（Skewed Tree）：
- 如果树退化成一个链表，树的高度 H = N。此时递归栈的深度会达到 N。空间复杂度为 O(N)。
平均情况（Balanced Tree）：
- 如果树是平衡的，树的高度 H = log N。此时递归栈的深度为 log N。空间复杂度为 O(log N)。