LC112 路径总和 · 逐题动画 · RuntimeScope

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

LC112 · 路径总和 · 工程执行实验室

root→leaf 路径 + remain 扣减 + 叶子结算

判断是否存在从根到叶的完整路径，使节点值之和等于 targetSum。每走一步扣当前节点；只有叶子才结算 remain == 0；左右子树任一侧成功即 true。

        5
       / \
      4   8
     /   / \
   11  13  4
  / \       \
 7   2       1

targetSum = 22 · 成功路径 5→4→11→2

root→leaf 完整路径 · 非任意子路径

核心 · remain 扣减 + 叶子结算

路径总和 = 是否存在一条从根节点到叶子节点的路径，使得路径上所有节点值之和等于 targetSum。

· 这题求的是从根到叶的完整路径，不是任意一段连续路径。
· 每进入一个节点，先从 remain 扣掉当前节点值：remain -= root.Val。
· remain == 0 只有在叶子节点才算成功；内部节点即使 remain == 0 也不能返回 true。
· 左右子树只要有一边递归返回 true，当前层就返回 true。

hasPathSum 四步骤

root == nil → false
targetSum -= root.Val
leaf → return targetSum == 0
return left || right

递归调用栈：remain 向下传，true 向上返

1.hasPathSum(node, remain) 压栈后，先 targetSum -= root.Val 扣减当前节点。
2.若当前是叶子，结算 return targetSum == 0；非叶继续递归左右。
3.任一侧返回 true，当前层即 true，沿栈向上传递最终答案。

1/8 · 题目定义

8 步分镜：

Step 1题目定义

展示题目：targetSum = 22，寻找 root→leaf 路径

给定二叉树与 targetSum = 22，判断是否存在一条从根到叶的完整路径，使路径上节点值之和等于 22。注意：必须是 root→leaf 的整条路径，不是任意一段子路径。示例成功路径 5 → 4 → 11 → 2，和为 22。

路径总和 = 是否存在一条从根节点到叶子节点的路径，使得路径上所有节点值之和等于 targetSum。
这题求的是从根到叶的完整路径，不是任意一段连续路径。
每进入一个节点，先从 remain 扣掉当前节点值：remain -= root.Val。
remain == 0 只有在叶子节点才算成功；内部节点即使 remain == 0 也不能返回 true。
左右子树只要有一边递归返回 true，当前层就返回 true。

为什么正确

路径总和 = 是否存在一条从根节点到叶子节点的路径，使得路径上所有节点值之和等于 targetSum。

状态表 · 当前发生了什么

当前节点	remain	调用栈	机器状态
—	22	[]	读题root→leaf · targetSum=22

remain 扣减 · targetSum = 22

初始 remain = 22

非叶（继续向下）

路径总和实验室·高亮 = 当前访问节点·黄线 = root→leaf 成功路径

递归栈 · 当前调用链

（空栈 · 尚未进入 DFS）

Go · hasPathSum

1func hasPathSum(root *TreeNode, targetSum int) bool {
2    if root == nil {
3        return false
4    }
6    targetSum -= root.Val
8    if root.Left == nil && root.Right == nil {
9        return targetSum == 0
10    }
12    return hasPathSum(root.Left, targetSum) || hasPathSum(root.Right, targetSum)
13}

复杂度

时间: O(n)
空间: O(h)

每个节点最多访问一次，n 为节点总数。

h 为树高。递归 DFS 调用栈深度等于树高：平衡树约 O(log n)，最坏单链退化 O(n)。不是 O(1) · 最坏 O(n)

面试回答

DFS 向下传剩余和 targetSum。每进入一个非空节点先 targetSum -= root.Val；若当前是叶子（左右都 nil），判断 targetSum == 0；否则递归左右子树，任一侧 true 即 true。空节点返回 false。时间 O(n)；空间 O(h)，最坏 O(n)，不是 O(1)。

常见错误

错误 1：中途 remain == 0 就返回 true

内部节点即使扣减后 remain 已为 0，也不能算成功——必须继续走到叶子，在 leaf 处判断 remain == 0。

错误 2：忘记必须是根到叶路径

题目要求完整 root→leaf 路径，不是任意子路径或跨分支拼接。不能在中途节点提前结束。

错误 3：把空节点当成成功

if root == nil { return false }。空节点不是合法路径终点，只有 leaf（左右均为 nil）才是结算点。

错误 4：空间复杂度误写成 O(1)

递归 DFS 需要系统调用栈保存每层暂停状态，空间是 O(h)，最坏单链 O(n)，不是 O(1)。

页面总结

LC112 的核心不是简单「求和」，而是三件事：

1. 每走一步扣当前节点（remain -= root.Val）
2. 只有走到叶子才结算（leaf && remain == 0）
3. 左右子树只要有一边成功，就返回 true

迁移练习

LC113 · 路径总和 II

同样 root→leaf + remain 扣减，但到叶且匹配时要收集整条 path 列表，需回溯 pop。

LC437 · 路径总和 III

不要求 root→leaf，任意起点终点路径即可，需前缀和或哈希，模型不同。

LC124 · 二叉树中的最大路径和

路径可拐弯、不必经过根，用全局 max + 后序汇报，不是 remain 扣减模型。