二叉树路径和计数：两种DFS实现的差异及错误原因解析

给定二叉树根节点与整数targetSum，需返回路径和等于targetSum的向下路径数量（路径无需始于根或终于叶）。错误实现代码在测试用例[1,null,2,null,3,null,4,null,5]、targetSum=3时返回3而非正确值2，核心问题是值为3的节点被重复统计。以下解析错误实现与正确实现的逻辑差异：

错误实现代码 #

# 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:

        self.res = 0

        def dfs(node, sum):
            if not node:
                return
            
            sum += node.val

            if sum == targetSum:
                self.res += 1
            
            dfs(node.left, 0)
            dfs(node.right, 0)

            dfs(node.left, sum)
            dfs(node.right, sum)

        dfs(root, 0)
        return self.res

正确实现代码 #

# 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:

        self.res = 0

        def dfs(node, sum):
            if not node:
                return

            sum += node.val

            if sum == targetSum:
                self.res += 1

            dfs(node.left, sum)
            dfs(node.right, sum)

        def traverse(node):
            if not node:
                return

            dfs(node, 0)
            traverse(node.left)
            traverse(node.right)

        traverse(root)
        return self.res

核心逻辑差异解析 #

正确实现的分层逻辑 #

正确实现采用两层独立遍历：

1. 外层traverse函数：遍历二叉树的每个节点，将每个节点作为新路径的起始点，调用内层dfs。
2. 内层dfs函数：从当前起始节点出发，向下累加路径和，仅统计以该节点为起点的所有符合条件的路径，过程中不会启动新的路径起点。

这种设计保证每个节点只会被作为路径起点一次，避免重复统计。

错误实现的逻辑混乱 #

错误实现将“启动新路径”和“延续当前路径”的逻辑强行塞进同一个dfs函数，导致重复统计：

• 每访问一个节点时，除了延续当前路径（调用dfs(node.left, sum)、dfs(node.right, sum)），还会立即启动以该节点左右子节点为起点的新路径（调用dfs(node.left, 0)、dfs(node.right, 0)）。
• 这就导致同一个子节点会被多个上层节点重复触发“作为新路径起点”的遍历。比如测试用例中的节点3：
  • 第一次被节点2触发（dfs(2,0)中的dfs(right,0)），统计路径[3]；
  • 第二次被节点1触发的dfs(2,1)中的dfs(right,0)再次触发，重复统计路径[3]；
  • 同时错误实现还会统计路径[1,2]，最终总计数变成3，超出正确值。

简言之，错误实现的核心问题是在路径遍历过程中重复启动新路径，导致同一有效路径被多次计数；而正确实现通过分层遍历，保证每个路径起点仅被处理一次，路径统计无重复。

内容的提问来源于stack exchange，提问作者Michael Xia