路径总和 II 图解题解

这道题到底在问什么

树

[5,4,8,11,2,13,7]

target

20

输出

[[5,4,11], [5,8,7]]

先想最直接的笨办法

笨办法也是最直接的办法:顺着树一杆子捅到底。每进一个节点,路径末尾多一个它、手里的「还差多少」就减掉它的值;一旦到叶子且「还差 0」,这条路就成了。然后退回去换条路再扎。（动画第 3 步）

最优解：一步一步想明白

1. 3笨办法也是最直接的办法:顺着树一杆子捅到底。每进一个节点,路径末尾多一个它、手里的「还差多少」就减掉它的值;一旦到叶子且「还差 0」,这条路就成了。然后退回去换条路再扎。
2. 4根=5, 叶子=11 / 2 / 13 / 7绿色的 11、2、13、7 是叶子(下面再没孩子)。一共 4 条根到叶子的路,我们要从里面挑出「加起来 = 20」的。
3. 54 条路:20 / 11 / 26 / 20提前对个答案(算法不会这样偷看,只是帮你心里有底):4 条路里 5→4→11 和 5→8→7 正好 20,另两条 11、26 不达标。下面跟着 DFS 一帧一帧真的走出来。
4. 6remain 一开始是 target=20。每进一个节点就 remain -= 它的值;到叶子时看 remain 是不是 0。先走左边(4 那片)两条,再走右边(8 那片)两条。
5. 7path=[5], remain = 20-5 = 15从根 5 出发:路径 = [5],remain 从 20 减去 5 → 还差 15。5 有孩子,不是叶子,先下探它的左孩子。
6. 8path=[5,4], remain = 15-4 = 11进入 4,路径 = [5,4],remain 再减 4 → 还差 11。5 成为路径节点。4 还有孩子,继续下探它的左孩子。
7. 9path=[5,4,11], remain = 11-11 = 0进入 11,路径 = [5,4,11],remain 减 11 → 还差 0!别急着收——还得确认 11 是不是叶子。
8. 1011 左右都空 ✓ 且 remain=0 ✓两个条件同时满足:11 是叶子(左右都空)、而且 remain 恰好 = 0。5→4→11 = 20,第一条达标路径!
9. 11结果 += [5,4,11]把 [5,4,11] 存进结果。这条分支探完了,接下来往回退到 4,去看它还没走的另一个孩子 2。
10. 12撤销 11, remain 加回 11 → 11从 11 退回 4:路径里的 11 被撤销、remain 把 11 加回来恢复成 11(这一步极关键!)。11 标记成已探完(变灰)。4 还有右孩子 2 没走。
11. 13path=[5,4,2], remain = 11-2 = 9进入 2,路径 = [5,4,2],remain 从 11 减 2 → 还差 9。2 是叶子吗?和够吗?
12. 142 是叶子 ✓ 但 remain=9 ≠ 0 ✗2 虽然是叶子,但 remain = 9 不为 0(5→4→2 只有 11,差 9)。不达标,不收。叶子不等于一定收——和必须恰好凑够。
13. 15撤销 2、4, remain 还原2 不达标,撤销退回 4;4 的左右孩子(11、2)都走过了,再撤销 4 退回根 5。整棵左子树(4 那片)全灰=探完,remain 还原回 15。
14. 16左边走完,轮到右孩子 85 的左孩子 4 整片探完。DFS 规矩:左边走干净才回头走右边。现在轮到 5 的右孩子 8,手里的 remain 此刻是 15。
15. 17path=[5,8], remain = 15-8 = 7进入 8,路径 = [5,8],remain 从 15 减 8 → 还差 7。8 还有孩子,继续下探它的左孩子 13。
16. 18path=[5,8,13], remain = 7-13 = -6进入 13,路径 = [5,8,13],remain 减 13 → 还差 -6(已经超了)。13 是叶子吗?和够吗?
17. 1913 是叶子 ✓ 但 remain=-6 ≠ 0 ✗13 是叶子,但 5→8→13 = 26,超了 6,remain = -6。不达标,不收。撤销 13、退回 8,去看它的右孩子 7。
18. 20撤销 13, remain 加回 13 → 7撤销 13:路径里的 13 去掉,remain 把 13 加回来 → 又回到 7。13 标灰。8 还有右孩子 7 没走,去探它。
19. 21path=[5,8,7], remain = 7-7 = 0进入 7,路径 = [5,8,7],remain 从 7 减 7 → 还差 0!再判一句:7 是叶子吗?
20. 227 是叶子 ✓ 且 remain=0 ✓7 是叶子且 remain 恰好 0,5→8→7 = 20,第二条达标路径!
21. 23结果 += [5,8,7]把 [5,8,7] 存进结果。7 探完,退回 8、再退回 5——此时 5 的左右孩子都走过了,整棵树遍历结束。
22. 24结果 = [[5,4,11], [5,8,7]]两条达标路径全找到:[5,4,11] 和 [5,8,7]。DFS + 回溯就是这样:深入到叶子判一次和,达标收下、不达标丢弃,退回换路再深入,直到走遍所有分支。
23. 25为什么走 8 那边时 remain 不是被 4 那边污染过的脏值?因为退回 5 时,4、11、2 都已撤销、remain 也加回到了 15。「进来减、出去加」让每条分支都从干净的状态出发。
24. 28和 LC257 是同一副骨架,只是把「拼字符串」换成「累加判等」。认准这三步,全排列 / 子集 / 组合一类回溯题全打通。
25. 30错误: 中间节点 remain 偶然=0 也被收假设有棵树某个中间节点走到时 remain 也恰好为 0,如果只判和不判叶子,就会错误地把一条没走到底的半截路径收进来。题目要的是「根到叶子」,叶子判定不能省。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int target) {
        dfs(root, target);
        return res;
    }
private:
    vector<vector<int>> res;
    vector<int> path;
    void dfs(TreeNode* node, int remain) {
        if (!node) return;
        path.push_back(node->val);          // 做选择
        remain -= node->val;                // 目标减掉它
        if (!node->left && !node->right && remain == 0) {
            res.push_back(path);            // 叶子且差0:收一份
        } else {
            dfs(node->left, remain);        // 探左
            dfs(node->right, remain);       // 探右
        }
        path.pop_back();                    // 撤销选择
    }
};

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> path = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        dfs(root, target);
        return res;
    }
    private void dfs(TreeNode node, int remain) {
        if (node == null) return;
        path.add(node.val);                 // 做选择
        remain -= node.val;                 // 目标减掉它
        if (node.left == null && node.right == null && remain == 0) {
            res.add(new ArrayList<>(path)); // 叶子且差0:收一份拷贝
        } else {
            dfs(node.left, remain);         // 探左
            dfs(node.right, remain);        // 探右
        }
        path.remove(path.size() - 1);       // 撤销选择
    }
}

复杂度

面试官可能追问