算法学习台/算法实验台/56 天打卡/141 题/LC112
题型地图56天全屏141题

当前：LC112 · 路径总和 · 首次出现于 Day 21 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

← LC110LC113 →
49 / 141回到 Day 21 卡片141 题索引
LC112Easy二叉树DFS根到叶路径

路径总和

把 targetSum 当成一张剩余预算票据：经过节点就扣掉它的值，只有在叶子处恰好扣完，才算找到合法路径。

题目是什么

判断是否存在一条根到叶路径，使路径节点值之和等于目标。

解决什么问题

同时约束路径起点、终点和总和，避免把部分路径误判为答案。

核心结论

递归传递剩余目标；只有叶子且 remaining == node.Val 才成功。

01交互算法精讲

先说结论：这道题到底解决什么

怎样在向下搜索时持续记录“还差多少”，并确保只有完整走到叶子的根到叶路径才能被判为成功？

中心结论：递归传递剩余目标；只有叶子且 remaining == node.Val 才成功。

读完必须能回答
  1. 1.为什么传递 remaining 比每次复制整条路径更直接？
  2. 2.为什么中途累计和达到目标仍不能返回 true？
  3. 3.树中允许负数时，为什么 remaining<0 不能作为剪枝条件？
02交互算法精讲

完整题目与题意拆解

给定二叉树 root 和整数 targetSum，判断是否存在一条从根节点到叶子节点的路径，使沿途节点值之和等于 targetSum。

叶子节点是左右孩子都为空的节点。路径不能提前停在仍有孩子的内部节点。

  • • 必须从根开始。
  • • 必须到叶子结束。
  • • 节点值可能为负数。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：5 → 4 → 11 → 2 的和为 22。

这不是任意两点之间的路径，也不是只要累计和途中等于目标就成功。

可以维护 currentSum，也可以把问题改写成剩余目标。每经过一个节点，把它的值从 remaining 中扣掉。

到达叶子时不必再扣一次：直接检查 remaining == node.Val。这个写法让成功条件和题目定义完全对齐。
动画 1 · 题意扫描

什么才算一条有效路径

镜头分别点亮根到叶路径和中途停止路径，用终点标记强调题目不接受在非叶节点提前结束。

Step 1/20%
根到叶路径
5
4
8
11
13
4
7
2
1
5 + 4 + 11 + 2 = 22
看完带走：路径必须从根出发并完整结束在叶子。
03交互算法精讲

第一层方案：暴力做法

最直观的方法是 DFS 携带 path 数组，到每个叶子时重新求和并比较。

如果每个叶子都重新求和或复制整条路径，链状或分支较多时会做重复工作。我们只需携带一个整数 remaining。

dfs(node, path)
  path = append(path, node.Val)
  到叶子时 sum(path) == targetSum
路径数组适合需要输出具体路径的 LC113；本题只返回 bool，剩余目标已经足够。
动画 2 · 暴力重复

累计到目标就返回为什么会误判

展示一个非叶节点处 remaining 已为零的场景，继续暴露下方孩子，从视觉上否定提前成功。

Step 1/20%
非叶不能提前成功
5
4
8
11
13
4
7
2
1
remaining = 0
isLeaf = false → 继续
看完带走：数值达到目标不等于路径已经满足终点条件。

优化方向：判断存在性只需要当前递归路径和剩余目标。失败时自然回退，成功时通过 OR 向上传递。

04交互算法精讲

整体地图：先做什么，再做什么

先把路径定义钉死：必须从根开始，在叶子结束。然后把全局目标改写成递归状态 remaining，沿路径经过一个节点就扣掉它的值。

只有到达叶子时，才检查 remaining 是否等于叶子值。非叶节点即使让剩余值变成 0，也必须继续走到叶子；左右子树只需任意一侧成功，所以结果用 OR 合并。

  • • remaining 压缩了当前路径已累加的历史。
  • • 叶子条件同时验证数值和路径终点。
  • • OR 表达“存在至少一条路径”。
这题最容易错的不是减法，而是忘记答案中的“叶子结束”四个字。
05交互算法精讲

把目标和变成沿路径递减的剩余额度

调用 hasPathSum(node,targetSum) 时，targetSum 表示从当前节点开始还需要凑出的总和。经过非叶节点后，计算 remaining=targetSum-node.Val，再把它交给左右孩子。

这个状态不需要保存完整路径，因为判断只关心路径和是否达到目标。每一层的 remaining 已经包含从根到父节点的全部历史。

目标 22 经过 5、4、11 后依次变成 17、13、2；到叶子 2 时 targetSum 恰好等于 node.Val，因此这条根到叶路径成功。
remaining 是一张随路径向下传递的账单，叶子负责最终结清。
动画 3 · 核心概念

剩余额度沿路径逐层递减

目标数字像账单一样随节点向下移动，每经过一个节点就扣除其值，并保留新的 remaining。

Step 1/30%
进入根节点
5
4
8
11
13
4
7
2
1
22 - 5 = 17
看完带走：remaining 已经浓缩了当前路径的全部历史。
06交互算法精讲

成功条件只放在叶子，分支结果使用 OR

空节点无法形成路径，返回 false。当前节点是叶子时，不再继续递归，直接判断 targetSum==root.Val；这一步同时确认路径终点和最后一个数值。

若当前节点不是叶子，扣掉 node.Val 后分别搜索左右子树。只要任意一侧存在合法路径即可，因此返回 leftOK || rightOK，并允许语言执行短路。

  • • 非叶节点 remaining==0 不能成功，因为路径尚未在叶子结束。
  • • nil 返回 false，避免把缺失孩子误当成合法终点。
  • • 题目允许负数，剩余值可能先负后正，不能按符号剪枝。
  • • 存在性问题用 OR，不是要求两边都找到的 AND。

先处理 nil，再判断当前节点是否为叶子。叶子返回目标匹配结果；非叶节点递归搜索左右子树。

左右结果使用 OR，因为题目问的是“是否存在至少一条”。

不能在 remaining < 0 时剪枝。节点值允许为负，后续值可能让总和重新回到目标。
动画 4 · 机制构建

叶子结算与 OR 分支

两个叶子依次比较 targetSum 与节点值，失败分支变灰，成功分支通过 OR 门向上返回。

Step 1/30%
失败叶子
5
4
8
11
13
4
7
2
1
remaining 2 != node.Val 7
看完带走：只在叶子结算，任意一条分支成功即可。
07交互算法精讲

remaining 不变量为什么准确代表当前路径

递归不变量是：进入 hasPathSum(node,targetSum) 时，targetSum 等于原目标减去从根到 node 父节点的路径和。初始调用没有经过任何节点，因此不变量成立。

在非叶节点扣除 node.Val 后传给孩子，新 targetSum 正好减去了到当前节点为止的路径和，不变量继续成立。

到叶子时检查 targetSum==node.Val，等价于原目标等于从根到该叶子的完整路径和。左右递归取 OR，恰好覆盖所有可能的根到叶路径。

数值条件和叶子条件在同一个时刻成立，才能构成题目要求的有效路径。
正确性抓手
  • • remaining 始终等于原目标减去当前节点之前路径上的节点和。
  • • 叶子检查 remaining == node.Val，恰好等价于完整根到叶路径和等于目标。
  • • 非叶节点将扣除当前值后的同一子问题交给左右子树，OR 正确表达存在性。
08交互算法精讲

完整执行过程

动画让一张剩余预算票据沿当前路径移动。每一步都显示具体减法，并区分失败叶子、成功叶子和非叶中间节点。

  1. 1从根 5 开始，目标 22 扣除 5 后，左右子树都收到 remaining=17。
  2. 2沿左侧经过 4，remaining 变为 13；再经过 11，下一步需要凑出 2。
  3. 3先到叶子 7，targetSum=2 与节点值 7 不同，这条路径失败。
  4. 4再到叶子 2，targetSum=2 与节点值相同，这条路径成功。
  5. 5成功通过 OR 逐层向上传播，根节点最终返回 true。
动画 5 · 完整执行

完整走过 5→4→11→2

从目标 22 开始同步播放每次扣减、失败回退和成功传播，始终显示当前节点与 remaining。

Step 1/60%
进入根节点
5
4
8
11
13
4
7
2
1
22 - 5 = 17
看完带走：状态向下传递，布尔结果沿调用栈向上返回。
09交互算法精讲

把动画和 Go 代码逐行对应

每一帧使用稳定的语义行 ID，不依赖容易漂移的数字行号。先观察分支为什么成立， 再看对应代码，而不是先背模板。

动画 6 · 代码映射

把路径定义锁进 Go 判断顺序

高亮 nil、叶子比较、扣除当前值和左右 OR，特别对照非叶零值与负数场景。

Step 1/40%
根到叶路径
5
4
8
11
13
4
7
2
1
5 + 4 + 11 + 2 = 22
看完带走：判断顺序保证代码不会把半条路径当成答案。
Step 1
合法路径必须从根走到叶子

只有起点、终点和总和三个条件同时满足，才能返回 true。

func · leaf-check
Step 2
经过 5，剩余目标变成 17

子树只需要回答：能否找到一条和为 17 的根到叶路径。

leaf-check · subtract-current · search-left
Step 3
经过 4，剩余目标变成 13

当前节点不是叶子，不能在这里做最终成功判断。

leaf-check · subtract-current · search-left
Step 4
经过 11，只剩目标 2

11 仍有两个孩子，哪怕累计和在这里达到目标也不能提前结束。

leaf-check · subtract-current · search-left
Step 5
叶子 7 没有刚好扣完

它是合法终点，却不满足总和条件，因此这条分支返回 false。

leaf-check · leaf-result
Step 6
叶子 2 恰好命中目标

根到叶、和值三个条件全部满足，这条路径返回 true。

leaf-check · leaf-result
Step 7
一边成功就能向上返回

题目只问是否存在一条路径，所以左右结果使用 OR。

search-left · search-right · return-either
Step 8
剩余变成 0，但不是叶子仍不能成功

题目要求根到叶路径，累计和提前命中不能替代叶子条件。

leaf-check · subtract-current
Step 9
节点有负数时不能按 remaining 剪枝

题目没有保证节点值全为正，符号不能证明分支必然失败。

subtract-current · return-either
Step 10
最坏检查整棵树

每个节点只处理一次，递归栈只保存当前根到节点路径。

return-either
10交互算法精讲

完整 Go 提交代码与最小测试

完整 Go 解法
1func hasPathSum(root *TreeNode, targetSum int) bool {2    if root == nil { return false }3 4    if root.Left == nil && root.Right == nil {5        return targetSum == root.Val6    }7 8    remaining := targetSum - root.Val9    leftOK := hasPathSum(root.Left, remaining)10    rightOK := hasPathSum(root.Right, remaining)11    return leftOK || rightOK12}
最小测试集合
// 主例：5→4→11→2
fmt.Println(hasPathSum(buildTree([]any{5, 4, 8, 11, nil, 13, 4, 7, 2}), 22)) // true
// 目标在非叶节点处达到，仍不能提前成功
fmt.Println(hasPathSum(buildTree([]any{1, 2}), 1)) // false
// 空树没有根到叶路径
fmt.Println(hasPathSum(nil, 0)) // false
// 负数节点存在，不能 remaining<0 就剪枝
fmt.Println(hasPathSum(buildTree([]any{-2, nil, -3}), -5)) // true
11交互算法精讲

正确性与复杂度

时间复杂度 O(n)

最坏情况下答案不存在，需要访问每个节点一次；存在答案时 OR 可能提前短路。

空间复杂度 O(h)

递归栈只保存当前根到节点的调用路径，深度等于树高 h。

12交互算法精讲

最容易写错的地方

错误 1

累计和中途达到目标就返回，没有检查叶子。

错误 2

把任意起点或任意终点路径当成答案。

错误 3

左右结果使用 AND，而题目只要求存在一条。

错误 4

remaining 小于 0 时错误剪枝，忽略负数节点。

13交互算法精讲

最后复盘：带走逻辑链

  1. 1.路径定义：根开始、叶子结束。
  2. 2.状态压缩：传递 remaining，而不是复制整条路径。
  3. 3.成功条件只在叶子判断。
  4. 4.需要输出所有路径时迁移到 LC113，并恢复 path 回溯。
面试表达
  1. 1.定义递归状态为当前节点和还需要凑出的 targetSum。
  2. 2.nil 返回 false；叶子直接判断 targetSum 是否等于当前值。
  3. 3.非叶节点把 targetSum-root.Val 传给左右子树，结果取 OR。
  4. 4.时间 O(n)，递归栈 O(h)；有负数，不能按 remaining<0 剪枝。