企业官网建设流程全解析

LeetCode 112 Path Sum 全解：四类 DFS/BFS 写法与二叉树根叶路径判定实战

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文围绕 LeetCode 112「Path Sum」展开：给定一棵二叉树与目标整数targetSum，判断是否存在一条从根节点到叶子节点的路径，使得路径上所有节点值之和等于targetSum。文档 articles/path-sum.md 给出了累积求和 DFS、目标递减 DFS、迭代 DFS、BFS 四种解法的完整直觉与多语言实现，本仓库在python/、cpp/、java/、go/、javascript/、csharp/、kotlin/、swift/、rust/等目录下均提供了对应源码（如 python/0112-path-sum.py、cpp/0112-path-sum.cpp）。读完本文，你将掌握该题的四种标准解法、各自的适用场景与复杂度边界，并能举一反三迁移到其他根叶路径类问题。

前置知识：动手前需要熟悉的三块基石

原文档明确指出，尝试本题前应具备以下基础：

• 二叉树（Binary Trees）：理解树的结构、根节点、叶子节点（无任何子节点的节点）以及遍历的基本概念；
• 深度优先搜索（DFS）：通过递归式树遍历，从根出发探索每一条通向叶子的路径；
• 递归（Recursion）：能够使用递归函数调用在树结构上游走。

这三者是理解后续四种解法的前提：DFS 天然枚举所有根叶路径，递归则让路径求和的状态随调用栈传递。

1. 解法一：累积求和的递归 DFS（DFS I）

直觉

从根向叶子遍历的同时把路径上经过的节点值累加起来。当到达叶子节点时，判断累积和是否等于targetSum。dfs会自然地覆盖所有根叶路径，因此非常适合本题。

算法步骤

1. 定义dfs(node, curSum)，返回从该节点出发是否存在满足条件的路径；
2. 若node为null，返回false；
3. 将node.val累加到curSum；
4. 若node是叶子节点（左右孩子均为空），返回curSum == targetSum；
5. 否则递归检查左右子树，只要其中一侧存在合法路径即返回true；
6. 以dfs(root, 0)启动搜索。

代码实现

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: def dfs(node, curSum): if not node: return False curSum += node.val if not node.left and not node.right: return curSum == targetSum return dfs(node.left, curSum) or dfs(node.right, curSum) return dfs(root, 0)

仓库中的 java/0112-path-sum.java 正是这一写法的直接实现：内部dfs方法携带currSum，到达叶子时比较currSum == targetSum。原文档中该解法的 Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 版本实现思路完全一致，均通过额外参数传递累积和。

时间复杂度与空间复杂度

• 时间复杂度：$O(n)$，其中n为节点数，每个节点恰好访问一次；
• 空间复杂度：$O(n)$，即递归栈的深度，最坏情况（退化成链表）下等于树高。

2. 解法二：目标递减的递归 DFS（DFS II）

直觉

与累加相反，这里从targetSum中不断减去节点值。到达叶子时，只需检查剩余目标是否为 0。这一写法避免了额外传递累积和参数，逻辑更紧凑，也是 cpp/0112-path-sum.cpp、go/0112-path-sum.go、csharp/0112-path-sum.cs、swift/0112-path-sum.swift 等仓库源码实际采用的风格。

算法步骤

1. 若root为null，返回false；
2. 从targetSum中减去root.val；
3. 若root是叶子，返回targetSum == 0；
4. 用更新后的目标递归调用左右孩子；
5. 只要任一子树找到合法路径即返回true。

代码实现

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False targetSum -= root.val return (self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum) or (not targetSum and not root.left and not root.right))

对比仓库实现可见多种等价变体：C++ 版本在减去root->val后，先判断“叶子且目标为零”再递归左右子树；Go 版本抽出了isChild辅助函数（go/0112-path-sum.go）判断叶子，Swift 版本则用hasChild做反向判断；Kotlin 版本通过扩展属性TreeNode.value访问节点值（kotlin/0112-path-sum.kt）。这些写法在语义上完全等价，可依据团队风格任选其一。

时间复杂度与空间复杂度

• 时间复杂度：$O(n)$；
• 空间复杂度：$O(n)$（递归栈）。

3. 解法三：显式栈的迭代 DFS

直觉

递归本质依赖调用栈，我们可以用显式栈模拟递归dfs。每个栈元素保存一个节点及其“到达目标还需的剩余和”。这种方式避免了极深树场景下的递归深度限制问题。

算法步骤

1. 若root为null，返回false；
2. 初始化栈为(root, targetSum - root.val)；
3. 栈非空时循环：
   • 弹出节点及其剩余和；
   • 若是叶子且剩余和为 0，返回true；
   • 若右孩子存在，压入(右孩子, 剩余和 - 右孩子.val)；
   • 若左孩子存在，压入(左孩子, 剩余和 - 左孩子.val)；
4. 栈空仍未找到合法路径，返回false。

代码实现

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False stack = [(root, targetSum - root.val)] while stack: node, curr_sum = stack.pop() if not node.left and not node.right and curr_sum == 0: return True if node.right: stack.append((node.right, curr_sum - node.right.val)) if node.left: stack.append((node.left, curr_sum - node.left.val)) return False

python/0112-path-sum.py 文件下半部分的迭代解法正是该思路，只是用列表de同时承担栈与（后文 BFS 解法的）队列角色。原文档中 C++ 用stack<pair<TreeNode*, int>>、Java 用双栈（Stack<TreeNode>与Stack<Integer>）分别存放节点与剩余和、Rust 用Vec<(Rc<RefCell<TreeNode>>, i32)>，核心逻辑均一致。

时间复杂度与空间复杂度

• 时间复杂度：$O(n)$；
• 空间复杂度：$O(n)$，显式栈在最坏情况下同样需要容纳树高数量的元素。

4. 解法四：队列驱动的广度优先搜索（BFS）

直觉

bfs按层推进，用队列保存每个节点及其剩余和。到达叶子时检查目标是否达成。BFS 能够系统地覆盖所有路径，且在“找到最短合法路径”这类衍生问题上具有天然优势。

算法步骤

1. 若root为null，返回false；
2. 初始化队列为(root, targetSum - root.val)；
3. 队列非空时循环：
   • 出队一个节点及其剩余和；
   • 若是叶子且剩余和为 0，返回true；
   • 若左孩子存在，入队(左孩子, 剩余和 - 左孩子.val)；
   • 若右孩子存在，入队(右孩子, 剩余和 - 右孩子.val)；
4. 未找到则返回false。

代码实现

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False queue = deque([(root, targetSum - root.val)]) while queue: node, curr_sum = queue.popleft() if not node.left and not node.right and curr_sum == 0: return True if node.left: queue.append((node.left, curr_sum - node.left.val)) if node.right: queue.append((node.right, curr_sum - node.right.val)) return False

注意 BFS 与迭代 DFS 的唯一区别是数据结构：BFS 使用 FIFO 队列（先进先出，逐层扩展），迭代 DFS 使用 LIFO 栈（后进先出，优先深入）。原文档中 Go 版本用切片模拟队列（queue = queue[1:]出队），Rust 用VecDeque，Kotlin/Swift 用ArrayDeque/数组，均是队列语义的标准实现。

时间复杂度与空间复杂度

• 时间复杂度：$O(n)$；
• 空间复杂度：$O(n)$，队列在满二叉树场景下最多同时容纳约一半节点。

5. 四种解法对比与选型建议

需要说明的是，四者时间复杂度均为 $O(n)$。对空间复杂度的更精确刻画，递归与迭代 DFS 实际取决于树高h（如 cpp/0112-path-sum.cpp 注释所写为 $O(h)$），而 BFS 取决于树的宽度；原文档统一以最坏情况 $O(n)$ 表述。

6. 常见陷阱：两道高频踩坑点

陷阱一：在非叶子节点就检查求和是否等于目标

最常见的错误是在每个节点（而非仅在叶子）比较当前和与目标。题目明确要求“根到叶子”的路径，因此即使某个内部节点的累积和恰好等于targetSum，也不应返回true。务必先确认左右孩子均为null，再比较和值。

陷阱二：在null节点上因目标为 0 而返回true

另一高频错误是：当递归到达null节点且此时targetSum恰好为 0 时错误地返回true。空树（根为null）无论目标为何都应返回false。null节点的基例必须始终返回false，和值检查只能在真正的叶子节点上进行。

对照 python/0112-path-sum.py、go/0112-path-sum.go 等仓库实现可以发现，所有正确写法都严格遵循“先判空返回 false，再判叶子比较和值”的顺序——这正是避开上述两个陷阱的关键。

7. 延伸：从 Path Sum 到系列进阶题

掌握本题后，同一根叶路径框架可以平滑迁移到仓库中的系列题目：

• 需要返回所有满足条件的路径而非仅判断是否存在时，参见 articles/binary-tree-maximum-path-sum.md 与仓库中0124系列源码（如 python/0124-binary-tree-maximum-path-sum.py）；
• 路径和不要求从根出发、允许任意节点起止并求最大值时，同样参考0124题解；
• 在网格/矩阵中做路径求和（DFS/BFS 变体）时，可参考 articles/minimum-path-sum.md、articles/minimum-falling-path-sum.md 及对应的0064、0931系列实现。

这些题目的共性都在于：维护路径上的累积状态，并在边界（叶子/网格终点）判定是否满足条件——这正是 Path Sum 四种解法教给我们的核心方法论。

小结

Path Sum 是二叉树 DFS 的经典入门题：它验证了递归遍历的直觉、多语言实现的一致性，以及“显式栈替代递归”“队列实现 BFS”两种工程化改写思路。结合本仓库0112系列源码（Python/C++/Java/Go/JavaScript/C#/Kotlin/Swift/Rust），你可以同时掌握抽象算法与具体语言惯用法。做题时牢记两点——只在叶子节点判和、空节点一律返回 false，即可稳定通过所有测试用例。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode