LeetCode 113. 路径总和 II

2026-07-24 HGNULB 约 5 分钟

文章信息 19 个分类 5 个标签

分类

LeetCode CodeTop 中等已解决需复习 50-100 字节跳动微软美团快手腾讯猿辅导百度滴滴京东拼多多网易小米虾皮

题目描述

✅ 113. 路径总和 II

题意分析

给定二叉树的根节点和目标和 targetSum，要求找出所有「从根节点到叶子节点」且节点值之和等于目标值的路径，并把每条路径的节点值序列都收集出来。注意要的不是「是否存在」，而是完整枚举每一条命中的路径。

「路径」的定义被题目锁死了：起点必须是根、终点必须是叶子（没有任何子节点的节点）。中途某个节点处的累计和恰好等于目标值并不算数，必须一路走到叶子再做判定。

约束里有一个关键信号：节点值范围是 -1000 到 1000，允许负数。这意味着「剩余目标已经小于 0」不代表这条路走不通——后面可能出现负值把和拉回来，所以不能靠剩余值提前放弃某个分支。节点数最多 5000，规模不大；边界情况是空树，此时不存在任何根到叶路径，应返回空列表。

解法：DFS 回溯记录根到叶路径

核心思路

问题关键：题目要求枚举所有根到叶子的合法路径。DFS 天然按路径向下搜索，配合回溯可以让不同分支复用同一个 path，无需在每层都复制路径。

为什么选该解法：进入节点时把值加入 path，离开时删除；每个节点只访问一次，只有找到答案时才复制路径。节点值允许为负数，因此不能根据剩余和的正负剪枝。

不变量/状态定义：进入 dfs(node, remain) 时，path 保存根到 node 父节点的路径，remain 是扣除这些节点后的剩余目标。加入 node.val 后，仅当当前节点是叶子且 remain == node.val 才命中。DFS 会遍历每条根到叶路径，因此所有合法答案都会被收集；写入结果时必须复制 path，避免后续回溯修改已保存路径。

解题步骤

初始化结果集和共享路径，从根节点带着 targetSum 开始 DFS。

空节点直接返回；进入非空节点时再将节点值加入路径。

若当前是叶子且剩余目标等于节点值，复制当前路径加入答案。

否则将 remain - node.val 传给左右子树。

返回父节点前删除路径末尾元素，恢复现场。

示例树中，路径 5 → 4 → 11 → 2 到达叶子时剩余值为 2，因此被收集；回溯后再搜索右子树，得到 5 → 8 → 4 → 5。

代码实现

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(root, targetSum, path, res);
        return res;
    }

    private void dfs(TreeNode node, int remain, List<Integer> path, List<List<Integer>> res) {
        if (node == null) {
            return;
        }

        path.add(node.val);
        if (node.left == null && node.right == null && remain == node.val) {
            // 当前路径会继续回溯修改，加入答案时必须复制。
            res.add(new ArrayList<>(path));
        } else {
            dfs(node.left, remain - node.val, path, res);
            dfs(node.right, remain - node.val, path, res);
        }
        path.remove(path.size() - 1);
    }
}

func pathSum(root *TreeNode, targetSum int) [][]int {
    res := make([][]int, 0)
    path := make([]int, 0)

    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, remain int) {
        if node == nil {
            return
        }

        path = append(path, node.Val)
        if node.Left == nil && node.Right == nil && remain == node.Val {
            // 复制当前路径，避免后续回溯覆盖结果。
            onePath := append([]int(nil), path...)
            res = append(res, onePath)
        } else {
            dfs(node.Left, remain-node.Val)
            dfs(node.Right, remain-node.Val)
        }
        path = path[:len(path)-1]
    }

    dfs(root, targetSum)
    return res
}

复杂度分析

时间复杂度：$O(n + S)$，S 为所有答案路径的总长度，因为每次命中都要复制路径；最坏可写作 $O(nh)$。

空间复杂度：$O(h)$，递归栈和当前路径都不超过树高；不计返回结果。

关键点总结

路径必须从根到叶，累计和中途等于目标不能提前收集。

添加和删除必须成对出现，保证兄弟分支互不污染。

保存答案时复制共享路径；Java 列表和 Go 切片都不能直接复用。

节点值可能为负数，不能用 remain < 0 剪枝。

易错点总结

直接保存 path 引用：回溯后答案会被清空或覆盖，必须复制快照。

不判断叶子：树 [1,2,3]、目标 1 会错误收集 [1]。

叶子条件使用 left == null || right == null：只有一个孩子的节点会被误判为叶子。

命中后提前返回而没有删除末尾节点：后续分支会混入上一条路径。

按 remain < 0 剪枝：[2,-1]、目标 1 会漏掉合法路径。

相似题目

题目	难度	考察点
112. 路径总和	简单	只判存在性，无需收集路径可提前返回
129. 求根节点到叶节点数字之和	中等	根叶路径压缩成十进制数再累加
257. 二叉树的所有路径	简单	收集全部根叶路径的字符串拼接版
404. 左叶子之和	简单	只统计左叶子，考察叶子方位判断
437. 路径总和 III	中等	起点不限于根，前缀和加哈希计数
1022. 从根到叶的二进制数之和	简单	位运算版的根叶路径累加
LCR 049. 求根节点到叶节点数字之和	中等	129 的镜像题
剑指 Offer 34. 二叉树中和为某一值的路径	中等	本题镜像题