题目描述
思路解析动画文字版
笨办法也是最直接的办法:顺着树一杆子捅到底。每进一个节点,路径末尾多一个它、手里的「还差多少」就减掉它的值;一旦到叶子且「还差 0」,这条路就成了。然后退回去换条路再扎。
先把这棵树看清楚：绿色的 11、2、13、7 是叶子(下面再没孩子)。一共 4 条根到叶子的路,我们要从里面挑出「加起来 = 20」的。
先把每条路的和心算一遍：提前对个答案(算法不会这样偷看,只是帮你心里有底):4 条路里 5→4→11 和 5→8→7 正好 20,另两条 11、26 不达标。下面跟着 DFS 一帧一帧真的走出来。
remain 一开始是 target=20。每进一个节点就 remain -= 它的值;到叶子时看 remain 是不是 0。先走左边(4 那片)两条,再走右边(8 那片)两条。
DFS 第 1 步 · 进根 5：从根 5 出发:路径 = [5],remain 从 20 减去 5 → 还差 15。5 有孩子,不是叶子,先下探它的左孩子。
下探 · 进 5 的左孩子 4：进入 4,路径 = [5,4],remain 再减 4 → 还差 11。5 成为路径节点。4 还有孩子,继续下探它的左孩子。
下探 · 进 4 的左孩子 11：进入 11,路径 = [5,4,11],remain 减 11 → 还差 0!别急着收——还得确认 11 是不是叶子。
判定 · 11 是叶子吗?和够吗?：两个条件同时满足:11 是叶子(左右都空)、而且 remain 恰好 = 0。5→4→11 = 20,第一条达标路径!
收第 1 条路径：把 [5,4,11] 存进结果。这条分支探完了,接下来往回退到 4,去看它还没走的另一个孩子 2。
回溯 · 从 11 退回 4：从 11 退回 4:路径里的 11 被撤销、remain 把 11 加回来恢复成 11(这一步极关键!)。11 标记成已探完(变灰)。4 还有右孩子 2 没走。
下探 · 进 4 的右孩子 2：进入 2,路径 = [5,4,2],remain 从 11 减 2 → 还差 9。2 是叶子吗?和够吗?
判定 · 2 达标吗?：2 虽然是叶子,但 remain = 9 不为 0(5→4→2 只有 11,差 9)。不达标,不收。叶子不等于一定收——和必须恰好凑够。
回溯 · 从 2 退回 4 再退回 5：2 不达标,撤销退回 4;4 的左右孩子(11、2)都走过了,再撤销 4 退回根 5。整棵左子树(4 那片)全灰=探完,remain 还原回 15。
根 5 的左孩子探完 · 换右孩子 8：5 的左孩子 4 整片探完。DFS 规矩:左边走干净才回头走右边。现在轮到 5 的右孩子 8,手里的 remain 此刻是 15。
下探 · 进 5 的右孩子 8：进入 8,路径 = [5,8],remain 从 15 减 8 → 还差 7。8 还有孩子,继续下探它的左孩子 13。
下探 · 进 8 的左孩子 13：进入 13,路径 = [5,8,13],remain 减 13 → 还差 -6(已经超了)。13 是叶子吗?和够吗?
判定 · 13 达标吗?：13 是叶子,但 5→8→13 = 26,超了 6,remain = -6。不达标,不收。撤销 13、退回 8,去看它的右孩子 7。
回溯 · 从 13 退回 8：撤销 13:路径里的 13 去掉,remain 把 13 加回来 → 又回到 7。13 标灰。8 还有右孩子 7 没走,去探它。
下探 · 进 8 的右孩子 7：进入 7,路径 = [5,8,7],remain 从 7 减 7 → 还差 0!再判一句:7 是叶子吗?
判定 · 7 达标吗?：7 是叶子且 remain 恰好 0,5→8→7 = 20,第二条达标路径!
收第 2 条路径：把 [5,8,7] 存进结果。7 探完,退回 8、再退回 5——此时 5 的左右孩子都走过了,整棵树遍历结束。
全部完成：两条达标路径全找到:[5,4,11] 和 [5,8,7]。DFS + 回溯就是这样:深入到叶子判一次和,达标收下、不达标丢弃,退回换路再深入,直到走遍所有分支。
为什么走 8 那边时 remain 不是被 4 那边污染过的脏值?因为退回 5 时,4、11、2 都已撤销、remain 也加回到了 15。「进来减、出去加」让每条分支都从干净的状态出发。
和 LC257 是同一副骨架,只是把「拼字符串」换成「累加判等」。认准这三步,全排列 / 子集 / 组合一类回溯题全打通。
雷区实演 · 只判和不判叶子：假设有棵树某个中间节点走到时 remain 也恰好为 0,如果只判和不判叶子,就会错误地把一条没走到底的半截路径收进来。题目要的是「根到叶子」,叶子判定不能省。
边界三连：特别注意:节点值可能是负数,所以不能像「全正数」那样一看到 remain 变负就停——必须老老实实走到叶子再判 remain==0。
面试追问：递归出口、与 LC112 的区别、迭代写法,是这题面试常被追的三点。
参考代码
class Solution: def pathSum(self, root, target): res, path = [], [] def dfs(node, remain): if not node: return path.append(node.val) # 做选择:加节点 remain -= node.val # 目标减掉它 if not node.left and not node.right and remain == 0: res.append(list(path)) # 叶子且差0:收一份拷贝 else: dfs(node.left, remain) # 探左 dfs(node.right, remain) # 探右 path.pop() # 撤销选择:去节点 dfs(root, target) return res复杂度
- 时间复杂度：O(n²)，n 个节点各访问一次;但每到一条达标叶子要拷贝整条路径(最长 O(n)),最坏 O(n) 条 → O(n²)
- 空间复杂度：O(n)，递归栈最深 = 树高 O(n)(斜树),加上 path 数组 O(n)
易错点
面试追问把动画讲成自己的话
追问递归出口是什么?
追问和 LC112 路径总和(只问是否存在)有什么区别?
追问怎么用迭代实现?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树展开为链表
LeetCode 114 · 中等 · 沿着 二叉树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题