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. 解法一累积求和的递归 DFSDFS I直觉从根向叶子遍历的同时把路径上经过的节点值累加起来。当到达叶子节点时判断累积和是否等于targetSum。dfs会自然地覆盖所有根叶路径因此非常适合本题。算法步骤定义dfs(node, curSum)返回从该节点出发是否存在满足条件的路径若node为null返回false将node.val累加到curSum若node是叶子节点左右孩子均为空返回curSum targetSum否则递归检查左右子树只要其中一侧存在合法路径即返回true以dfs(root, 0)启动搜索。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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. 解法二目标递减的递归 DFSDFS II直觉与累加相反这里从targetSum中不断减去节点值。到达叶子时只需检查剩余目标是否为 0。这一写法避免了额外传递累积和参数逻辑更紧凑也是 cpp/0112-path-sum.cpp、go/0112-path-sum.go、csharp/0112-path-sum.cs、swift/0112-path-sum.swift 等仓库源码实际采用的风格。算法步骤若root为null返回false从targetSum中减去root.val若root是叶子返回targetSum 0用更新后的目标递归调用左右孩子只要任一子树找到合法路径即返回true。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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。每个栈元素保存一个节点及其“到达目标还需的剩余和”。这种方式避免了极深树场景下的递归深度限制问题。算法步骤若root为null返回false初始化栈为(root, targetSum - root.val)栈非空时循环弹出节点及其剩余和若是叶子且剩余和为 0返回true若右孩子存在压入(右孩子, 剩余和 - 右孩子.val)若左孩子存在压入(左孩子, 剩余和 - 左孩子.val)栈空仍未找到合法路径返回false。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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 Falsepython/0112-path-sum.py 文件下半部分的迭代解法正是该思路只是用列表de同时承担栈与后文 BFS 解法的队列角色。原文档中 C 用stackpairTreeNode*, int、Java 用双栈StackTreeNode与StackInteger分别存放节点与剩余和、Rust 用Vec(RcRefCellTreeNode, i32)核心逻辑均一致。时间复杂度与空间复杂度时间复杂度$O(n)$空间复杂度$O(n)$显式栈在最坏情况下同样需要容纳树高数量的元素。4. 解法四队列驱动的广度优先搜索BFS直觉bfs按层推进用队列保存每个节点及其剩余和。到达叶子时检查目标是否达成。BFS 能够系统地覆盖所有路径且在“找到最短合法路径”这类衍生问题上具有天然优势。算法步骤若root为null返回false初始化队列为(root, targetSum - root.val)队列非空时循环出队一个节点及其剩余和若是叶子且剩余和为 0返回true若左孩子存在入队(左孩子, 剩余和 - 左孩子.val)若右孩子存在入队(右孩子, 剩余和 - 右孩子.val)未找到则返回false。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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 用VecDequeKotlin/Swift 用ArrayDeque/数组均是队列语义的标准实现。时间复杂度与空间复杂度时间复杂度$O(n)$空间复杂度$O(n)$队列在满二叉树场景下最多同时容纳约一半节点。5. 四种解法对比与选型建议解法数据结构遍历顺序时间空间适用场景递归 DFS累加调用栈深度优先$O(n)$$O(n)$最直观面试首选逻辑最易解释递归 DFS递减调用栈深度优先$O(n)$$O(n)$参数更少、代码更紧凑迭代 DFS显式栈深度优先$O(n)$$O(n)$树极深、担心递归爆栈时BFS队列广度优先$O(n)$$O(n)$需按层遍历或扩展求最短路径类问题时需要说明的是四者时间复杂度均为 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 112 Path Sum 全解：四类 DFS/BFS 写法与二叉树根叶路径判定实战
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. 解法一累积求和的递归 DFSDFS I直觉从根向叶子遍历的同时把路径上经过的节点值累加起来。当到达叶子节点时判断累积和是否等于targetSum。dfs会自然地覆盖所有根叶路径因此非常适合本题。算法步骤定义dfs(node, curSum)返回从该节点出发是否存在满足条件的路径若node为null返回false将node.val累加到curSum若node是叶子节点左右孩子均为空返回curSum targetSum否则递归检查左右子树只要其中一侧存在合法路径即返回true以dfs(root, 0)启动搜索。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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. 解法二目标递减的递归 DFSDFS II直觉与累加相反这里从targetSum中不断减去节点值。到达叶子时只需检查剩余目标是否为 0。这一写法避免了额外传递累积和参数逻辑更紧凑也是 cpp/0112-path-sum.cpp、go/0112-path-sum.go、csharp/0112-path-sum.cs、swift/0112-path-sum.swift 等仓库源码实际采用的风格。算法步骤若root为null返回false从targetSum中减去root.val若root是叶子返回targetSum 0用更新后的目标递归调用左右孩子只要任一子树找到合法路径即返回true。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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。每个栈元素保存一个节点及其“到达目标还需的剩余和”。这种方式避免了极深树场景下的递归深度限制问题。算法步骤若root为null返回false初始化栈为(root, targetSum - root.val)栈非空时循环弹出节点及其剩余和若是叶子且剩余和为 0返回true若右孩子存在压入(右孩子, 剩余和 - 右孩子.val)若左孩子存在压入(左孩子, 剩余和 - 左孩子.val)栈空仍未找到合法路径返回false。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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 Falsepython/0112-path-sum.py 文件下半部分的迭代解法正是该思路只是用列表de同时承担栈与后文 BFS 解法的队列角色。原文档中 C 用stackpairTreeNode*, int、Java 用双栈StackTreeNode与StackInteger分别存放节点与剩余和、Rust 用Vec(RcRefCellTreeNode, i32)核心逻辑均一致。时间复杂度与空间复杂度时间复杂度$O(n)$空间复杂度$O(n)$显式栈在最坏情况下同样需要容纳树高数量的元素。4. 解法四队列驱动的广度优先搜索BFS直觉bfs按层推进用队列保存每个节点及其剩余和。到达叶子时检查目标是否达成。BFS 能够系统地覆盖所有路径且在“找到最短合法路径”这类衍生问题上具有天然优势。算法步骤若root为null返回false初始化队列为(root, targetSum - root.val)队列非空时循环出队一个节点及其剩余和若是叶子且剩余和为 0返回true若左孩子存在入队(左孩子, 剩余和 - 左孩子.val)若右孩子存在入队(右孩子, 剩余和 - 右孩子.val)未找到则返回false。代码实现# Definition for a binary tree node. # class TreeNode: # def __init__(self, val0, leftNone, rightNone): # 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 用VecDequeKotlin/Swift 用ArrayDeque/数组均是队列语义的标准实现。时间复杂度与空间复杂度时间复杂度$O(n)$空间复杂度$O(n)$队列在满二叉树场景下最多同时容纳约一半节点。5. 四种解法对比与选型建议解法数据结构遍历顺序时间空间适用场景递归 DFS累加调用栈深度优先$O(n)$$O(n)$最直观面试首选逻辑最易解释递归 DFS递减调用栈深度优先$O(n)$$O(n)$参数更少、代码更紧凑迭代 DFS显式栈深度优先$O(n)$$O(n)$树极深、担心递归爆栈时BFS队列广度优先$O(n)$$O(n)$需按层遍历或扩展求最短路径类问题时需要说明的是四者时间复杂度均为 $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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考