LeetCode 112. 路径总和
题目描述
题意分析
判断是否存在一条从根节点出发、沿父子连接一直到叶子节点的路径，使路径中所有节点值之和等于
targetSum。只需返回是否存在，不需要记录路径；任何一条满足即可。叶子节点必须左右孩子都为空，中途节点或某个缺失的孩子都不能充当终点。空树不存在根到叶子的路径，即使目标为零也返回
false。节点值可能为负数，因此不能只依据当前和是否超过目标判断后面有没有答案。
解法：DFS 递减剩余路径和
核心思路
[!blue]
给递归函数一个明确含义：
hasPathSum(node, remain)判断，从当前node开始到它所在子树的某片叶子，是否存在节点和等于remain的路径。原问题就是从根节点出发、剩余目标为targetSum的这次调用。若当前节点为空，这里没有可作为路径起点的节点，应直接返回
false。若当前节点是叶子，整条剩余路径只有它自己，只需比较remain == node.val；不能把叶子判断替换成空节点处比较剩余值，否则只有一个孩子的中间节点可能沿空分支被误认为路径终点。若当前节点不是叶子，任何完整路径都必须先包含它，再进入左子树或右子树。因此扣除当前值，把
remain - node.val分别交给两个孩子，只要其中一个子问题成立，当前问题就成立。这既覆盖所有根到叶子的选择，也不会把不同分支的节点和混合起来。左右子调用接收的是同一个扣除结果，但整数参数按值传递，左分支的递归不会改变右分支需要的目标，不需要手动恢复数值。逻辑或会在左侧已找到答案时直接结束，符合本题只判断存在性的要求；如果两侧都不成立才返回
false。
解题步骤
- 当前节点为空时返回
false。- 当前节点左右孩子都为空时，返回目标是否等于当前节点值。
- 否则计算
remain = targetSum - root.val，把当前节点的贡献扣掉一次。- 用同一个
remain递归判断左右子树，返回两次结果的逻辑或。
代码实现
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if (root == null) {
return false;
}
// 目标仍包含当前节点，只有完整到达叶子才判断相等。
if (root.left == null && root.right == null) {
return targetSum == root.val;
}
// 扣掉当前节点后，把剩余目标交给孩子。
int remain = targetSum - root.val;
return hasPathSum(root.left, remain) || hasPathSum(root.right, remain);
}
}
func hasPathSum(root *TreeNode, targetSum int) bool {
if root == nil {
return false
}
// 目标仍包含当前节点，只有完整到达叶子才判断相等。
if root.Left == nil && root.Right == nil {
return targetSum == root.Val
}
// 扣掉当前节点后，把剩余目标交给孩子。
remain := targetSum - root.Val
return hasPathSum(root.Left, remain) || hasPathSum(root.Right, remain)
}
复杂度分析
- 时间复杂度：$O(n)$，最坏访问所有节点；找到匹配路径后可以提前结束。
- 空间复杂度：$O(h)$，
h为树高，递归栈只保存当前路径。平衡树为 $O(\log n)$，退化为链时为 $O(n)$。
关键点总结
[!green]
- 递归目标仍包含当前节点，因此叶子直接比较当前值，非叶子才把扣除后的目标传给孩子。
- 只有真实叶子能够结束路径，空节点表示没有路径而不是成功匹配。
- 子树之间是“任意一条成立即可”的关系，返回值使用逻辑或。
- 目标按值传递，不会发生左右分支互相污染，不需要另建路径列表。
易错点总结
[!yellow]
- 在空节点处用剩余目标为零判断成功，会把中间节点的缺失孩子当作终点；空节点必须返回
false。- 只要当前值等于剩余目标就返回成功，可能在尚未到达叶子时提前结束。
- 用左右孩子为空的“或”条件判断叶子，会把只有一个孩子的节点误判为叶子。
- 先扣除当前值，又在叶子处与当前值比较，相当于重复扣除；必须统一剩余目标的含义。
- 按剩余目标的正负剪枝，会忽略后续负数节点可能补足路径和的情况。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 113. 路径总和 II | 中等 | 路径范围同为根到叶，原题输出全部匹配路径，本题只需判断是否存在。 |
| 437. 路径总和 III | 中等 | 原题允许任意祖先作为起点，本题起点固定为根且终点必须是叶子。 |
| 257. 二叉树的所有路径 | 简单 | 回溯维护从根到当前节点的路径；本题判断是否存在目标和叶路径，该题输出所有根到叶的字符串路径。 |
| 129. 求根节点到叶节点数字之和 | 中等 | 回溯维护从根到当前节点的路径；本题判断是否存在目标和叶路径，该题逐层按十进制累加根到叶数字。 |
| 666. 路径总和 IV | 中等 | 路径总和系列。IV 用深度和位置编码树，仍沿根到叶累计路径和，最终对所有叶子的结果求和。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！