LeetCode 113. Path Sum II 题解
LeetCode 113. Path Sum II 题解
题目描述
给你二叉树的根节点root和一个整数目标和targetSum，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
叶子节点是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]示例 3：
输入：root = [1,2], targetSum = 0 输出：[]解题思路
方法：深度优先搜索（DFS）+ 回溯
思路：
- 使用深度优先搜索遍历二叉树
- 记录当前路径和当前路径的和
- 当到达叶子节点时，检查当前路径的和是否等于目标和
- 如果等于，将当前路径加入结果列表
- 使用回溯法，在递归返回时移除当前节点，以便探索其他路径
复杂度分析：
- 时间复杂度：O(n²)，其中 n 是二叉树的节点个数。每个节点只被访问一次，但是需要复制路径，最坏情况下路径长度为 O(n)。
- 空间复杂度：O(n)，递归调用的栈空间取决于二叉树的深度，最坏情况下为 O(n)。
代码实现
方法：深度优先搜索（DFS）+ 回溯
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: result = [] path = [] def dfs(node, current_sum): if not node: return # 将当前节点加入路径 path.append(node.val) current_sum += node.val # 检查是否是叶子节点且路径和等于目标和 if not node.left and not node.right and current_sum == targetSum: result.append(path.copy()) # 递归搜索左子树和右子树 dfs(node.left, current_sum) dfs(node.right, current_sum) # 回溯：移除当前节点 path.pop() dfs(root, 0) return result测试用例
测试用例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
测试用例 2：
输入：root = [1,2,3], targetSum = 5
输出：[]
测试用例 3：
输入：root = [1,2], targetSum = 0
输出：[]
总结
本题是二叉树的经典问题，主要考察对二叉树遍历和回溯的理解和应用。通过使用深度优先搜索和回溯，我们可以高效地找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
深度优先搜索的核心思想是：遍历二叉树，记录当前路径和当前路径的和，当到达叶子节点时，检查路径和是否等于目标和。回溯的核心思想是：在递归返回时移除当前节点，以便探索其他路径。
这种方法不仅适用于路径总和 II 问题，还可以应用于许多其他需要遍历二叉树并记录路径的场景。掌握深度优先搜索和回溯的思想，对于解决这类问题非常重要。