原来的解法：只过root

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        ans = 0
        def dfs(root, targetSum, s):
            if not root:
                return
            s += root.val
            if s == targetSum:
                nonlocal ans
                ans += 1
            dfs(root.left, targetSum, 0)
            dfs(root.right, targetSum, 0)
        dfs(root, targetSum, 0)
        return ans

官方递归解法：

python

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        def rootSum(root, targetSum):
            if root is None:
                return 0

            ret = 0
            if root.val == targetSum:
                ret += 1

            ret += rootSum(root.left, targetSum - root.val)
            ret += rootSum(root.right, targetSum - root.val)
            return ret

        if root is None:
            return 0

        ret = rootSum(root, targetSum)
        ret += self.pathSum(root.left, targetSum)
        ret += self.pathSum(root.right, targetSum)
        return ret

这段代码其实用了「分治＋遍历每个节点作为起点」的思路，保证了所有可能的路径都会被统计到，不只是从整棵树的根节点开始的那些。具体来看：

rootSum(root, targetSum) 只负责计算“以当前节点 root 开头、向下延伸”的所有路径中，有多少条和为 targetSum。
- 它先检查自己（if root.val == targetSum），再递归到左右子树，把剩余的目标和 targetSum - root.val 继续往下找。
- 这样能找到所有「从这个节点开始，到它后代节点结束」的合法路径。

外层的 pathSum(root, targetSum) 则是把上面那个「以当前节点为起点」的统计，推广到整棵树的每一个节点：

python

ret = rootSum(root, targetSum)           # 统计所有以 root 为起点的路径
ret += self.pathSum(root.left, targetSum)  # 再去左子树，把每个左子树节点当做“新起点”
ret += self.pathSum(root.right, targetSum) # 再去右子树，把每个右子树节点当做“新起点”

对每一个节点都调用一次 rootSum，就等于把这棵树里的所有可能起点都遍历一遍。

为什么能覆盖所有路径？
- 在「路径」的定义里，只要是向下（parent → child）的连续节点序列，都被合法地考虑到了。
- 任意一条路径，要么它是从某个节点开始的，那么肯定会被当做起点去调用 rootSum，要么它位于某条更高的子树里，也会被递归到那棵子树的那次调用中去统计。

因此，虽然你看 rootSum 只管「过当前节点、连到左右子树」的那些，但外层递归又会把「当前节点」对换成整棵树里的每一个节点。两层加起来，就枚举了所有可能的「自上而下」的路径。

两层递归

这里其实用了两层“递归”：

rootSum 这层递归
- 作用是：以当前节点 root 作为路径的“起点”，沿着父→子往下，统计有多少条路径之和等于 targetSum。
- 它自己内部递归调用自己，分别进入 root.left 和 root.right，相当于在“同一条起点”下，把所有可能的向下分支都走一遍。
pathSum 这层递归
- 作用是：把 整棵树 上的每一个节点都当做一次新的“起点”去调用 rootSum。
- 它在算完从 当前 root 出发的所有路径数之后，再递归地对 root.left 和 root.right 重复同样的流程，确保没有遗漏“从子节点开始”的那些路径。

text

ret = rootSum(root, targetSum)          # 统计“以 root 为起点”的路径
ret += self.pathSum(root.left, targetSum)   # 再把左子树当整棵树，去统计“以左子节点为起点”的所有路径
ret += self.pathSum(root.right, targetSum)  # 同理，对右子树也做一次

如果只用 rootSum，只能统计从根节点开始的路径；如果只用 pathSum 但不调用 rootSum，又得不到“累加经过减去当前节点值后继续向下匹配”的细节。两层递归配合，就能枚举 所有可能的起点（外层）和 从起点往下的所有路径（内层），从而保证整棵树里任意一段向下连续路径都被统计到。

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        if not root:
            return 0
        def dfs(root, targetSum):
            if not root:
                return 0
            ret = 0
            if root.val == targetSum:
            # 如果当前节点的值正好就等于我们还剩下的目标和 targetSum，说明从这个节点到自身构成了一条有效路径，计数加 1。
                ret += 1
            # 我们将 “还剩下的目标和” 减去当前节点的 root.val，递归去左右子树里继续找，以便统计所有以 当前节点 为起点的、经过子节点的路径。
            ret += dfs(root.left, targetSum - root.val)
            ret += dfs(root.right, targetSum - root.val)
            return ret

        ret = 0
        # 它在算完从 当前 root 出发的所有路径数之后，再 递归地对 root.left 和
        # root.right 重复同样的流程，确保没有遗漏“从子节点开始”的那些路径。
        ret += dfs(root, targetSum)
        ret += self.pathSum(root.left, targetSum)
        ret += self.pathSum(root.right, targetSum)
        return ret

复杂度分析

时间复杂度：O(N2)，其中 N 为该二叉树节点的个数。对于每一个节点，求以该节点为起点的路径数目时，则需要遍历以该节点为根节点的子树的所有节点，因此求该路径所花费的最大时间为 O(N)，我们会对每个节点都求一次以该节点为起点的路径数目，因此时间复杂度为 O(N2)。

空间复杂度：O(N)，考虑到递归需要在栈上开辟空间。

前缀和

python

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        ans = 0
        cnt = defaultdict(int)
        cnt[0] = 1

        def dfs(node: Optional[TreeNode], s: int) -> None:
            if node is None:
                return

            nonlocal ans
            s += node.val
            # 把 node 当作路径的终点，统计有多少个起点
            ans += cnt[s - targetSum]

            cnt[s] += 1
            dfs(node.left, s)
            dfs(node.right, s)
            cnt[s] -= 1  # 恢复现场

        dfs(root, 0)
        return ans

作者：灵茶山艾府
链接：https://leetcode.cn/problems/path-sum-iii/solutions/2784856/zuo-fa-he-560-ti-shi-yi-yang-de-pythonja-fmzo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。