LeetCode 112题：二叉树路径总和的DFS解法详解

1. 题目解析与核心思路LeetCode 112题路径总和是一个经典的二叉树遍历问题。题目要求我们判断给定的二叉树中是否存在一条从根节点到叶子节点的路径使得路径上所有节点值的和等于给定的目标值。这道题看似简单却涵盖了二叉树遍历、递归思维和边界条件处理等多个重要编程概念。1.1 题目具体要求给定一个二叉树的根节点和一个目标和判断该树中是否存在根节点到叶子节点的路径这条路径上所有节点值相加等于目标和。叶子节点是指没有子节点的节点。示例输入 5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1 目标和 22 输出true 解释存在路径 5→4→11→2其和为 221.2 解题思路分析这道题的核心在于如何高效地遍历所有可能的路径并检查它们的和。深度优先搜索(DFS)是解决这类问题的理想选择因为它天然适合处理树形结构的遍历问题。DFS会沿着一条路径尽可能深入地搜索直到找到叶子节点或者不满足条件然后回溯继续搜索其他路径。2. 深度优先搜索算法详解2.1 DFS基本概念深度优先搜索是一种用于遍历或搜索树或图的算法。在二叉树中DFS有三种基本遍历方式前序遍历根→左→右中序遍历左→根→右后序遍历左→右→根对于路径总和问题前序遍历是最自然的选择因为我们需要在访问子节点前先处理当前节点的值。2.2 递归实现DFS递归是实现DFS最直观的方式。对于路径总和问题递归的思路可以描述为从根节点开始用目标和减去当前节点的值如果当前节点是叶子节点检查剩余和是否为0如果不是叶子节点递归检查左右子树def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: # 叶子节点 return targetSum root.val return hasPathSum(root.left, targetSum - root.val) or hasPathSum(root.right, targetSum - root.val)2.3 迭代实现DFS虽然递归实现简洁但了解迭代实现也很重要特别是对于大型树结构可以避免递归深度过大导致的栈溢出问题。def hasPathSum(root, targetSum): 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 False3. 算法优化与边界条件3.1 提前终止优化在实际实现中我们可以添加提前终止条件来优化性能。例如当当前路径和已经超过目标和时可以立即停止该路径的进一步搜索。def hasPathSum(root, targetSum): if not root: return False if not root.left and not root.right: return targetSum root.val if root.left and hasPathSum(root.left, targetSum - root.val): return True if root.right and hasPathSum(root.right, targetSum - root.val): return True return False3.2 边界条件处理正确处理边界条件是算法正确性的关键空树情况直接返回False单节点树直接比较节点值和目标和负数值节点不能因为当前和为负就提前终止因为后续可能有更大的负值使总和满足条件4. 复杂度分析与实际应用4.1 时间复杂度分析在最坏情况下我们需要访问树中的所有节点因此时间复杂度为O(N)其中N是树中的节点数。4.2 空间复杂度分析递归实现的空间复杂度取决于树的深度最好情况平衡树O(logN)最坏情况退化为链表O(N)迭代实现的空间复杂度同样取决于树的深度。4.3 实际应用场景路径总和问题及其变体在实际中有广泛应用文件系统中查找特定大小的文件路径决策树中寻找满足特定条件的决策路径游戏开发中的路径规划网络路由中的路径选择5. 常见错误与调试技巧5.1 常见错误类型忽略空树情况错误判断叶子节点必须同时没有左右子节点在迭代实现中错误处理栈的顺序前序/后序错误处理目标和为0的情况5.2 调试技巧打印递归调用树观察参数变化使用小规模的测试用例逐步验证检查边界条件处理是否正确对于迭代实现可以打印栈的状态来跟踪执行过程6. 相关题目扩展掌握路径总和问题后可以尝试解决以下变体题目LeetCode 113. 路径总和 II - 找出所有满足条件的路径LeetCode 437. 路径总和 III - 不限定从根节点开始LeetCode 124. 二叉树中的最大路径和 - 寻找最大路径和LeetCode 129. 求根到叶子节点数字之和 - 处理路径组成的数字7. 个人实战经验分享在实际刷题过程中我发现以下几点特别重要先画图理解问题手动计算几个例子明确递归终止条件这是递归正确性的关键对于迭代实现注意栈的压入顺序会影响遍历顺序测试时要考虑各种边界情况包括空树、单节点树、负数值等一个容易忽略的细节是只有当节点是叶子节点时才能判断是否满足条件。我曾经犯过在非叶子节点就判断的错误导致某些情况下得到错误结果。对于性能优化在递归调用前先检查子节点是否存在可以避免不必要的函数调用栈。例如if root.left and hasPathSum(root.left, targetSum - root.val): return True这种写法比直接调用hasPathSum更高效因为它避免了不必要的递归调用。