作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
题目描述
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
示例
示例
输入：
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1
目标和 = 22
输出：True（存在路径 5 -> 4 -> 11 -> 2，和为 22）
方法一：递归深度优先搜索（DFS）
解题步骤
- 递归函数定义：定义一个辅助函数来递归检查每个节点，传递当前的累计总和。
- 递归终止条件：如果当前节点是叶子节点，并且其值加上累计总和等于目标值，返回
True。 - 递归逻辑：递归检查当前节点的左右子节点。
Python 示例
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def hasPathSum(root, sum): """ 检查二叉树中是否存在根到叶子的路径总和等于给定值 :param root: TreeNode, 二叉树的根节点 :param sum: int, 目标和 :return: bool """ if not root: return False sum -= root.val if not root.left and not root.right: # 检查是否为叶子节点 return sum == 0 return hasPathSum(root.left, sum) or hasPathSum(root.right, sum)
算法分析
- 时间复杂度：(O(n))，每个节点访问一次。
- 空间复杂度：(O(h))，递归栈的深度，其中 (h) 是树的高度。
方法一使用递归深度优先搜索（DFS）来寻找是否存在从根到叶子的路径，其和等于给定的目标值。虽然这种方法直观且易于实现，但在某些情况下可能会进行不必要的递归调用，尤其是在不平衡的树中。因此，我们可以通过一些技术改进它，以提高效率和实用性。
方法一改进：优化的递归DFS
改进点
- 短路逻辑：在递归过程中，一旦找到符合条件的路径，即可立即停止进一步的递归，避免不必要的计算。
- 减少参数传递：可以通过直接修改传递的
sum参数来减少参数的数量，这样可以稍微降低递归调用的开销。
改进后的 Python 示例
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def hasPathSum(root, sum): """ 使用优化的DFS检查是否存在从根到叶的路径总和等于给定值 :param root: TreeNode, 二叉树的根节点 :param sum: int, 目标和 :return: bool """ if not root: return False # 检查是否到达叶子节点并且路径总和匹配 if not root.left and not root.right: return root.val == sum # 递归检查左右子树 sum -= root.val return hasPathSum(root.left, sum) or hasPathSum(root.right, sum) # 示例调用 root = TreeNode(5, TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2)), None), TreeNode(8, TreeNode(13), TreeNode(4, None, TreeNode(1)))) print(hasPathSum(root, 22)) # 输出: True
算法分析
- 时间复杂度：改进后，时间复杂度依然为 (O(n))，因为每个节点仍然需要至多被访问一次。
- 空间复杂度：改进后，空间复杂度也为 (O(h))，其中 (h) 是树的高度，对应于递归栈的最大深度。通过短路逻辑，可能在找到第一个有效路径时减少空间使用。
优劣势比较
- 优点：
- 短路逻辑可以减少在找到有效路径后的不必要递归，提高效率。
- 直接修改
sum减少了参数传递，稍微优化了递归的性能。
- 缺点：
- 递归深度依然依赖于树的高度，对于极端不平衡的树依然可能导致较高的空间复杂度。
这种改进使得递归方法在实际应用中更加高效，尤其是在早期找到符合条件的路径时，能够显著减少计算量。
方法二：迭代使用栈
解题步骤
- 使用栈：利用栈存储每个节点及其对应的路径总和。
- 迭代逻辑：迭代访问每个节点，更新路径总和，检查叶子节点的路径总和。
Python 示例
def hasPathSum(root, sum): if not root: return False stack = [(root, root.val)] while stack: node, curr_sum = stack.pop() if not node.left and not node.right and curr_sum == sum: 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
算法分析
- 时间复杂度：(O(n))，每个节点最多被访问一次。
- 空间复杂度：(O(n))，在最坏的情况下，栈中需要存储所有节点。
方法二使用迭代的方式通过栈实现深度优先搜索（DFS），检查是否存在从根到叶的路径，其和等于给定目标值。虽然迭代方法减少了递归可能引起的栈溢出问题，但其管理栈的方式仍有改进空间，特别是在如何更高效地处理节点和路径和的记录。
方法二改进：优化的迭代DFS
改进点
- 使用结构体或类：为了减少重复的元素推入和弹出操作，可以创建一个简单的类或结构体来存储节点以及到该节点为止的累积和，这样可以使代码更加清晰且减少错误。
- 早停机制：在发现第一个符合条件的叶子节点时立即停止所有操作，避免不必要的迭代。
改进后的 Python 示例
from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right class PathNode: def __init__(self, node, current_sum): self.node = node self.current_sum = current_sum def hasPathSum(root, targetSum): if not root: return False stack = deque([PathNode(root, root.val)]) # 使用PathNode来存储节点和当前路径和 while stack: path_node = stack.pop() node = path_node.node current_sum = path_node.current_sum # 检查是否到达叶子节点且路径和符合条件 if not node.left and not node.right and current_sum == targetSum: return True # 将非空子节点和相应的路径和压入栈 if node.right: stack.append(PathNode(node.right, current_sum + node.right.val)) if node.left: stack.append(PathNode(node.left, current_sum + node.left.val)) return False # 示例调用 root = TreeNode(5, TreeNode(4, TreeNode(11, TreeNode(7), TreeNode(2)), None), TreeNode(8, TreeNode(13), TreeNode(4, None, TreeNode(1)))) print(hasPathSum(root, 22)) # 输出: True
算法分析
- 时间复杂度：优化后，时间复杂度仍为 (O(n))，每个节点最多被访问一次。
- 空间复杂度：优化后，空间复杂度也为 (O(n))，在最坏的情况下可能需要存储所有节点。
优劣势比较
- 优点：
- 代码结构更清晰，通过使用
PathNode类减少了代码的复杂度和出错概率。 - 早停机制提高了效率，避免了不必要的迭代。
- 缺点：
- 空间复杂度相比递归方法有所提高，因为迭代方法需要显式使用栈存储节点。
通过这种改进，迭代方法在处理大型数据集时更加健壮且易于维护，尤其适用于深度较大的树结构，减少了递归可能导致的栈溢出风险。
应用示例
这些方法在计算机科学中广泛应用于路径查找、网络流量分析、资源管理等领域，其中需要确定从一个点到另一个点的可达性或路径成本。
欢迎关注微信公众号 数据分析螺丝钉
