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

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

← LC112LC114 →
50 / 141回到 Day 22 卡片141 题索引
LC113数据结构二叉树 · 路径和 II递归回执树

路径总和 II

找所有根到叶路径和=22 的路径列表。

题目是什么

找所有根到叶路径和=22 的路径列表。

解决什么问题

当前调用等待哪些子问题回执，返回值对父节点意味着什么？

核心结论

回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。

01交互算法精讲

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

怎样从“找所有根到叶路径和=22 的路径列表。”推导出 二叉树 · 路径和 II，并证明每次状态变化都不会漏掉答案？

中心结论：回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。

读完必须能回答
  1. 1.暴力方案在哪里重复计算，为什么仍然是正确基线？
  2. 2.当前调用等待哪些子问题回执，返回值对父节点意味着什么？
  3. 3.不变量“回溯离开结点要 pop 恢复 path。”为什么能保证算法安全前进？
02交互算法精讲

完整题目与题意拆解

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。

在本站主例中，找所有根到叶路径和=22 的路径列表。

算法最终需要得到或观察：[[5,4,11,2], [5,8,4,5]]

把题目翻译成状态
  • • 输入：找所有根到叶路径和=22 的路径列表。
  • • 机器需要维护：path 栈、remain、结果集。
  • • 最终可观察结果：[[5,4,11,2], [5,8,4,5]]
动画 1 · 题意扫描

先看清算法到底要维护什么

先建立输入、目标、输出和第一批状态，不急着进入模板。

Step 1/20%
题目与输入建立输入、目标与算法心智

找 root→leaf 和 = 22

正在加载算法场景...
03交互算法精讲

第一层方案：暴力做法

从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

动画 2 · 暴力重复

重复工作究竟发生在哪里

把重复读取或重复搜索的区域明确标出，再决定优化必须保存什么。

Step 1/20%
先做对：建立暴力基线枚举所有候选并完整验证

找 root→leaf 和 = 22

正在加载算法场景...
优化方向：回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。
04交互算法精讲

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

  1. 1建模把输入翻译成“递归回执树”，明确答案需要观察什么。
  2. 2状态只维护 path 栈、remain、结果集。
  3. 3转移每一步按照 回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。
  4. 4收尾读取 [[5,4,11,2], [5,8,4,5]]，并复核边界与复杂度。
05交互算法精讲

递归回执树：核心概念

先用一句话定义递归函数返回什么，父节点才能正确合并。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：path 栈、remain、结果集。

核心不变量
  • • 回溯离开结点要 pop 恢复 path。
  • • 收集答案必须 ans.push([...path]) 副本。
动画 3 · 核心概念

建立“递归回执树”心智模型

用主例建立核心状态，先预测下一步，再公开正确分支和理由。

Step 1/30%
题目与输入建立输入、目标与算法心智

找 root→leaf 和 = 22

正在加载算法场景...
06交互算法精讲

核心机制：状态如何一步步变化

这一题是第 257 题和第 112 题的组合增强版

回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。

执行过程中持续维护：path 栈、remain、结果集。

正确性依赖以下不变量：回溯离开结点要 pop 恢复 path。；收集答案必须 ans.push([...path]) 副本。

面试时可以压缩为：DFS+回溯,维护 path 与 remain,叶且 remain==0 时 push 副本;时间 O(N+K·H) 最坏 O(N²),辅助空间 O(H)。

落到当前题，执行机制可以压缩为：回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

动画 4 · 机制构建

一次状态转移为什么成立

集中观察一次选择、计算和状态写回，让变量变化与原因同时出现。

Step 1/50%
经过 5,remain → 17dfs with remain

路径 5

正在加载算法场景...
07交互算法精讲

正确性证明：为什么不会漏答案

初始化

初始化：算法开始时，全部合法候选仍在状态表示范围内；回溯离开结点要 pop 恢复 path。

保持

保持：执行“回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。”时，只删除已经能证明不可能的候选，并把新信息写回 path 栈、remain、结果集。

终止

终止：没有待处理状态或达到命中条件时，当前可观察结果就是“[[5,4,11,2], [5,8,4,5]]”。

正确性抓手不是“样例跑通”，而是每一帧结束后仍能复述：回溯离开结点要 pop 恢复 path。；收集答案必须 ans.push([...path]) 副本。
08交互算法精讲

完整执行过程

  1. 1题目与输入找所有根到叶路径和=22 的路径列表。 因为：回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。
  2. 2经过 5,remain → 17继续向下。 因为：只有根到叶路径才计数。
  3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
  4. 4叶子 7,remain=-5,不命中检查是否等于 target。 因为：只有根到叶路径才计数。
  5. 5经过 8,remain → 9继续向下。 因为：只有根到叶路径才计数。
  6. 6叶子 5,remain=-9,不命中检查是否等于 target。 因为：只有根到叶路径才计数。
  7. 7叶子 4,remain=5,不命中检查是否等于 target。 因为：只有根到叶路径才计数。
  8. 8收尾与复杂度[[5,4,11,2], [5,8,4,5]] 因为：时间 O(N + K·H)，最坏 O(N²) · 空间 O(H) 辅助；输出 O(K·H)。回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。
动画 5 · 完整执行

从输入完整走到可观察结果

从主例第一帧运行到答案，时间轴始终显示当前状态、因果解释和下一步。

Step 1/80%
题目与输入建立输入、目标与算法心智

找 root→leaf 和 = 22

正在加载算法场景...
09交互算法精讲

把动画和 Go 代码逐行对应

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

动画 6 · 代码映射

让每个动作都落到 Go 分支

重新执行关键分支，只显示当前代码附近窗口，并说明这行为什么在此刻运行。

Step 1/60%
DFS 维护剩余和remain = target - node.val

找 root→leaf 和 = 22

正在加载算法场景...
10交互算法精讲

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

完整 Go 解法
// TreeNode define
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

// 解法一
func pathSum(root *TreeNode, sum int) [][]int {
	var slice [][]int
	slice = findPath(root, sum, slice, []int(nil))
	return slice
}

func findPath(n *TreeNode, sum int, slice [][]int, stack []int) [][]int {
	if n == nil {
		return slice
	}
	sum -= n.Val
	stack = append(stack, n.Val)
	if sum == 0 && n.Left == nil && n.Right == nil {
		slice = append(slice, append([]int{}, stack...))
		stack = stack[:len(stack)-1]
	}
	slice = findPath(n.Left, sum, slice, stack)
	slice = findPath(n.Right, sum, slice, stack)
	return slice
}

// 解法二
func pathSum1(root *TreeNode, sum int) [][]int {
	if root == nil {
		return [][]int{}
	}
	if root.Left == nil && root.Right == nil {
		if sum == root.Val {
			return [][]int{{root.Val}}
		}
	}
	path, res := []int{}, [][]int{}
	tmpLeft := pathSum(root.Left, sum-root.Val)
	path = append(path, root.Val)
	if len(tmpLeft) > 0 {
		for i := 0; i < len(tmpLeft); i++ {
			tmpLeft[i] = append(path, tmpLeft[i]...)
		}
		res = append(res, tmpLeft...)
	}
	path = []int{}
	tmpRight := pathSum(root.Right, sum-root.Val)
	path = append(path, root.Val)

	if len(tmpRight) > 0 {
		for i := 0; i < len(tmpRight); i++ {
			tmpRight[i] = append(path, tmpRight[i]...)
		}
		res = append(res, tmpRight...)
	}
	return res
}
最小测试集合
func main() {
    // 1. 主例
    //    输入：mode="path-sum", values=[5,4,8,11,null,13,4,7,2,null,null,5,1], target=22
    //    期望：[[5,4,11,2], [5,8,4,5]]
    //
    // 2. 失败 / 未命中
    //    检查：忘记 push [...path] 副本会被后续修改。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC112 路径和；LC437 路径和 III
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

11交互算法精讲

正确性与复杂度

时间复杂度 O(N + K·H)，最坏 O(N²)

执行过程中只保留仍可能影响答案的状态。回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。

空间复杂度 O(H) 辅助；输出 O(K·H)

额外状态主要用于维护：path 栈、remain、结果集。

终局不变量
  • • 回溯离开结点要 pop 恢复 path。
  • • 收集答案必须 ans.push([...path]) 副本。
12交互算法精讲

最容易写错的地方

错误 1

忘记 push [...path] 副本会被后续修改。

错误 2

找到一条就 return 会漏解。

错误 3

非叶 remain==0 不算成功。

边界复查

必须额外检查空输入、单元素、未命中或不可达情况，以及恰好落在边界的输入。

13交互算法精讲

最后复盘：带走逻辑链

  1. 1题意找所有根到叶路径和=22 的路径列表。
  2. 2重复从每个节点重新遍历子树会重复计算；递归让每棵子树只计算一次并向父节点返回摘要。
  3. 3优化回溯 DFS:path 记录,到叶且 sum 匹配 push 副本。
  4. 4证明回溯离开结点要 pop 恢复 path。；收集答案必须 ans.push([...path]) 副本。
  5. 5复杂度时间 O(N + K·H)，最坏 O(N²)，空间 O(H) 辅助；输出 O(K·H)
面试表达：DFS+回溯,维护 path 与 remain,叶且 remain==0 时 push 副本;时间 O(N+K·H) 最坏 O(N²),辅助空间 O(H)。
迁移练习
  • • LC112 路径和
  • • LC437 路径和 III