路径总和 II:收下一条路,离开必须弹出
共享一份 path。进节点就 append,到叶子且剩余为 0 就拷贝;无论成不成,返回前都要把自己 pop 掉。
DFS + 回溯:进入节点时把值加入 path,剩余值减掉;到叶子且剩余为 0 时把 path 的副本加入结果;无论成不成,返回前把最后加入的节点从 path 移除,恢复现场。时间 O(n²)(复制路径),空间 O(h)。
给定二叉树根和整数 targetSum,返回所有从根到叶子、节点值之和等于 targetSum 的路径。只要和、不要路径是 LC112;只要路径字符串、不要和是 LC257。
主例树根 5,左 4-11 再分 7 与 2,右 8 再分 13 与 4(4 下还有 5),targetSum=22。两条合法路:[5,4,11,2] 与 [5,8,4,5]。演示先走到 [5,4,11,7],剩余 -5,不是目标;再走到 [5,4,11,2] 命中。
本文要回答:为什么收集必须用共享切片加回溯,以及主例从 7 回到 11 时若不 pop,2 会接到怎样的脏路上。
缺口是可复用的路径现场
LC112 往下传一个剩余值,叶子处剩余为 0 就返回 true,现场不用保存。这题要交出每一条具体节点序列。若每条路都从根再走一遍,前缀 5-4-11 会被算两次。缺的是一份正在走的 path:进一层加上当前值,离开一层拿掉当前值,兄弟分支才能从同一截前缀接着试。
合同是:进入 n,path 追加 n.Val,remain 减去 n.Val。若 n 是叶子且 remain==0,把 path 拷贝进答案——必须拷贝,后面的 pop 会改原切片。然后照样递归左右(叶子的左右是空,马上返回)。函数结束前执行 path = path[:len-1],把自己从尾部拿掉。
remain 按值传递,左右孩子各拿一份减过之后的数,互不影响。path 不是按值传递,它是共享底层数组。所以 remain 不用「加回去」,path 必须 pop。LC257 用字符串当参数,拼接出新串,才可以不 pop;这题要的是整数切片,离开就要 pop。
用手走主例左脊。根 5,path=[5],剩余 17。左 4,path=[5,4],剩余 13。11 进入,path=[5,4,11],剩余 2。左叶 7:path=[5,4,11,7],剩余 2-7=-5,不是 0,不收。演示第一帧停在这里。返回前弹出 7,path 回到 [5,4,11]。
11 的右叶 2:path=[5,4,11,2],剩余 0,叶子,拷贝收下。演示第二帧。弹出 2,再弹出 11、4,回到根。右子树同样节奏:5-8-13 和是 26,叶子不收;5-8-4-5 和是 22,再收一条。终帧两条都在。若 7 返回时忘了 pop,走到 2 时 path 会是 [5,4,11,7,2],和与内容全错。
非叶子即使当前和已经等于 22 也不能收——题目要根到叶。负数节点让剩余变大,仍要继续走,不能按「剩余为负就剪」一刀切,除非题目保证全是正数。复制路径让时间落到 O(n²):最坏每条根到叶都长 O(n)。
恢复现场进来 append、出去 pop,path 在每个兄弟入口都是同一截前缀。主例弹出 7 之后,2 才能接到 [5,4,11] 上。remain 是值,不必对称加回。
Go:DFS + 回溯
func pathSum(root *TreeNode, target int) [][]int {res := [][]int{}path := []int{}var dfs func(*TreeNode, int)dfs = func(n *TreeNode, remain int) {if n == nil { return }path = append(path, n.Val)remain -= n.Valif n.Left == nil && n.Right == nil && remain == 0 {res = append(res, append([]int{}, path...))}dfs(n.Left, remain)dfs(n.Right, remain)path = path[:len(path)-1]}dfs(root, target)return res}
1path 在闭包外共享。所有分支改的是同一份切片。
2一进节点就 append 并减 remain。主例进 7 后剩余 -5。
3只有叶子且剩余 0 才拷贝。中途和等于目标不收。
4左右各拿当前 remain。值传递,右边看不到左边再减过的数。
5最后一行 pop。主例离开 7 后 path 必须回到 [5,4,11],2 才能接对。
总结
共享 path:进就加、离就弹。主例 22 收下两条,7 那条剩余 -5 要 pop。
- LC112 只传剩余;这题还要切片现场。忘了 pop,兄弟会接到脏尾。
- 记录必须拷贝。LC257 用字符串传参可以不 pop,切片不行。
- 非叶子不收。剩余变负也不一定能剪,节点可能是负数。