作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
题目描述
给你一个二叉树和一个目标和 targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
示例
示例
输入：
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1
目标和 targetSum = 22
输出：[[5,4,11,2], [5,8,4,5]]
方法一：递归深度优先搜索（DFS）
解题步骤
- 递归函数定义：定义一个辅助函数来递归检查每个节点，传递当前路径和累积路径列表。
- 递归终止条件：如果当前节点是叶子节点，并且其值加上累计总和等于目标值，将路径添加到结果列表。
- 递归逻辑：递归检查当前节点的左右子节点，并更新路径列表和当前和。
Python 示例
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def pathSum(root, targetSum): results = [] def dfs(node, current_sum, path): if not node: return current_sum += node.val path.append(node.val) if not node.left and not node.right and current_sum == targetSum: results.append(path.copy()) # 注意复制列表 dfs(node.left, current_sum, path) dfs(node.right, current_sum, path) path.pop() # 回溯 dfs(root, 0, []) return results
算法分析
- 时间复杂度：(O(n))，每个节点访问一次。
- 空间复杂度：(O(h))，递归栈的深度，其中 (h) 是树的高度。
方法一使用递归的深度优先搜索（DFS）来寻找所有符合条件的路径。虽然这种方法直观且能有效地解决问题，但它可能会因为大量的递归调用而在空间复杂度上较高，特别是在不平衡的树中。以下是对方法一的几项改进，旨在优化其性能和可读性。
方法一改进：优化的递归DFS
改进点
- 短路逻辑：一旦达到一个叶子节点并且路径和不符合目标值，立即回溯，减少不必要的递归。
- 减少中间数组操作：通过直接传递路径而不是在每次递归中创建新的数组拷贝，可以减少内存的使用和可能的垃圾回收。
改进后的 Python 示例
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def pathSum(root, targetSum): results = [] def dfs(node, current_sum, path): if not node: return # 更新当前路径和 current_sum += node.val # 将当前节点值添加到路径中 path.append(node.val) # 检查当前节点是否为叶子节点且路径和是否符合条件 if not node.left and not node.right: if current_sum == targetSum: results.append(list(path)) # 添加一份路径的拷贝 # 递归遍历左右子节点 if node.left: dfs(node.left, current_sum, path) if node.right: dfs(node.right, current_sum, path) # 回溯，移除当前节点值 path.pop() dfs(root, 0, []) return results
算法分析
- 时间复杂度：优化后，时间复杂度仍为 (O(n))，因为每个节点最多被访问一次。
- 空间复杂度：优化后的空间复杂度主要取决于递归的深度，最坏情况下为 (O(h))，其中 (h) 是树的高度。使用回溯法避免了不必要的数组拷贝，减少了内存占用。
优劣势比较
- 优点：
- 减少内存占用，尤其是通过避免不必要的数组拷贝。
- 短路逻辑减少了无效的路径探索，提高了算法效率。
- 缺点：
- 代码复杂度略有增加，需要仔细管理路径变量和回溯机制。
通过这种改进，递归方法在处理复杂或深度较大的树结构时变得更加高效和稳健。这种优化使得方法既能快速找到解决方案，又能控制内存的使用，适合在资源受限的环境中运行。
方法二：迭代使用栈
解题步骤
- 使用栈：利用栈存储每个节点及其对应的路径总和和当前路径。
- 迭代逻辑：迭代访问每个节点，更新路径总和，检查叶子节点的路径总和。
Python 示例
def pathSum(root, targetSum): if not root: return [] results = [] stack = [(root, root.val, [root.val])] while stack: node, curr_sum, path = stack.pop() if not node.left and not node.right and curr_sum == targetSum: results.append(path) if node.right: stack.append((node.right, curr_sum + node.right.val, path + [node.right.val])) if node.left: stack.append((node.left, curr_sum + node.left.val, path + [node.left.val])) return results
算法分析
- 时间复杂度：(O(n))，每个节点至多访问一次。
- 空间复杂度：(O(n))，在最坏的情况下，栈中需要存储所有节点。
优劣势对比
| 方法 | 优点 | 缺点 |
| DFS递归 | 代码直观易懂；适合复杂树结构 | 高空间复杂度，依赖于树的高度 |
| 迭代使用栈 | 明确控制遍历过程；适合避免递归引起的问题 | 空间复杂度较高，代码复杂度高于递归 |
应用示例
这些方法广泛应用于计算机科学的多个领域，尤其是在路径和网络流中，路径总和问题可用于决策支持系统、资源管理和网络数据传输路径优化等方面。
欢迎关注微信公众号 数据分析螺丝钉
