LeetCode 题解工作台
路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 示例 1： 输入： root = [10,5,-3,3,2,…
3
题型
8
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们可以运用前缀和的思想，对二叉树进行递归遍历，同时用哈希表 统计从根节点到当前节点的路径上各个前缀和出现的次数。 我们设计一个递归函数 $\textit{dfs(node, s)}$，表示当前遍历到的节点为 ，从根节点到当前节点的路径上的前缀和为 。函数的返回值是统计以 节点及其子树节点作为路径终点且路径和为 的路径数目。那么答案就是 $\textit{dfs(root, 0)}$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：3
提示:
- 二叉树的节点个数的范围是
[0,1000] -109 <= Node.val <= 109-1000 <= targetSum <= 1000
解题思路
方法一：哈希表 + 前缀和 + 递归
我们可以运用前缀和的思想，对二叉树进行递归遍历，同时用哈希表 统计从根节点到当前节点的路径上各个前缀和出现的次数。
我们设计一个递归函数 ，表示当前遍历到的节点为 ，从根节点到当前节点的路径上的前缀和为 。函数的返回值是统计以 节点及其子树节点作为路径终点且路径和为 的路径数目。那么答案就是 。
函数 的递归过程如下：
- 如果当前节点 为空，则返回 。
- 计算从根节点到当前节点的路径上的前缀和 。
- 用 表示以当前节点为路径终点且路径和为 的路径数目，其中 即为 中前缀和为 的个数。
- 将前缀和 的计数值加 ，即 。
- 递归地遍历当前节点的左右子节点，即调用函数 和 ，并将它们的返回值相加。
- 在返回值计算完成以后，需要将当前节点的前缀和 的计数值减 ，即执行 。
- 最后返回答案。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点个数。
# 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) -> int:
def dfs(node, s):
if node is None:
return 0
s += node.val
ans = cnt[s - targetSum]
cnt[s] += 1
ans += dfs(node.left, s)
ans += dfs(node.right, s)
cnt[s] -= 1
return ans
cnt = Counter({0: 1})
return dfs(root, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the specific approach, but the DFS method generally works in O(N) time, where N is the number of nodes in the tree. The space complexity depends on the stack used in DFS or the hash map in the prefix sum approach, typically O(N) as well. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate implement DFS with state tracking or prefix sums to handle path sum?
- question_mark
How well does the candidate optimize for memory usage and performance?
- question_mark
Does the candidate demonstrate awareness of potential edge cases, such as empty trees or negative values?
常见陷阱
外企场景- error
Failing to account for paths that don’t start at the root or end at a leaf.
- error
Inefficient traversal that results in redundant calculations without optimization.
- error
Not considering negative values in the tree, which can affect the sum calculations.
进阶变体
外企场景- arrow_right_alt
Handling binary trees with negative node values.
- arrow_right_alt
Adapting the algorithm to find paths with sums greater than or less than the target.
- arrow_right_alt
Extending the problem to count paths of a fixed length or with additional constraints.