LeetCode 题解工作台
路径总和 II
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1： 输入： root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们从根节点开始，递归遍历所有从根节点到叶子节点的路径，并记录路径和。当遍历到叶子节点时，如果此时路径和等于 `targetSum`，则将此路径加入答案。 时间复杂度 ，其中 是二叉树的节点数。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉树的根节点 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 输出：[]
提示：
- 树中节点总数在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解题思路
方法一：DFS
我们从根节点开始，递归遍历所有从根节点到叶子节点的路径，并记录路径和。当遍历到叶子节点时，如果此时路径和等于 targetSum，则将此路径加入答案。
时间复杂度 ，其中 是二叉树的节点数。空间复杂度 。
# 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]]:
def dfs(root, s):
if root is None:
return
s += root.val
t.append(root.val)
if root.left is None and root.right is None and s == targetSum:
ans.append(t[:])
dfs(root.left, s)
dfs(root.right, s)
t.pop()
ans = []
t = []
dfs(root, 0)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N^2) in the worst case for a skewed tree because copying the path takes O(N) per leaf, with N nodes. Space complexity is O(N) for recursion stack and path storage. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks about recursive vs iterative DFS approaches for path tracking.
- question_mark
Questions about handling negative values in node sums or targetSum.
- question_mark
Wants explanation on why backtracking is essential to avoid incorrect path accumulation.
常见陷阱
外企场景- error
Forgetting to backtrack and remove the last node, corrupting future paths.
- error
Returning paths before reaching leaf nodes, which violates root-to-leaf definition.
- error
Not handling empty trees or single-node cases properly, leading to runtime errors.
进阶变体
外企场景- arrow_right_alt
Return only the first valid path instead of all paths.
- arrow_right_alt
Modify the problem to find paths summing to a target in a n-ary tree instead of binary tree.
- arrow_right_alt
Count the number of paths instead of returning the path lists.