LeetCode 题解工作台
路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。 叶子节点 是指没有子节点的节点。 示例 1： 输入： root …
4
题型
7
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
从根节点开始，递归地对树进行遍历，并在遍历过程中更新节点的值为从根节点到该节点的路径和。当遍历到叶子节点时，判断该路径和是否等于目标值，如果相等则返回 `true`，否则返回 `false`。 时间复杂度 ，其中 是二叉树的节点数。对每个节点访问一次。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径： (1 --> 2): 和为 3 (1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。
示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解题思路
方法一：递归
从根节点开始，递归地对树进行遍历，并在遍历过程中更新节点的值为从根节点到该节点的路径和。当遍历到叶子节点时，判断该路径和是否等于目标值，如果相等则返回 true，否则返回 false。
时间复杂度 ，其中 是二叉树的节点数。对每个节点访问一次。
# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(root, s):
if root is None:
return False
s += root.val
if root.left is None and root.right is None and s == targetSum:
return True
return dfs(root.left, s) or dfs(root.right, s)
return dfs(root, 0)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you account for negative and zero values when calculating path sums?
- question_mark
Can you implement both DFS and BFS versions and explain their trade-offs in memory and recursion?
- question_mark
Will you correctly identify leaf nodes and handle empty or single-node trees in your solution?
常见陷阱
外企场景- error
Failing to correctly check that a node is a leaf before comparing the sum to target can produce false positives.
- error
Not handling null or empty trees leads to runtime errors or incorrect false results.
- error
Overwriting or mismanaging cumulative sums in recursive DFS can cause wrong answers when multiple paths exist.
进阶变体
外企场景- arrow_right_alt
Find all root-to-leaf paths that sum to target instead of a boolean output.
- arrow_right_alt
Return the number of root-to-leaf paths that sum to the target value.
- arrow_right_alt
Determine if any path (not necessarily root-to-leaf) sums to target, allowing mid-tree endpoints.