LeetCode 补充题 181. 二叉树中和为目标值的所有向下路径
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 437. 路径总和 III
:::
给定二叉树
root和整数target，返回所有节点值之和等于target的非空路径。路径只能从父节点走向子节点，可从任意节点开始，也可在任意节点结束。
结果顺序不限，不同节点组成的路径分别输出。
示例 1：
输入：
root = [10,5,-3,3,2,null,11,3,-2,null,1], target = 8
输出：[[5,3],[5,2,1],[-3,11]]
解释： 树按层序表示，null为空节点。三条路径都向下，且不要求从根10开始。
示例 2：
输入：
root = [1,1,1], target = 1
输出：[[1],[1],[1]]
解释： 三个不同节点各自构成一条路径，不能按值序列去重。
提示：
- 采用
n≤1000的二叉树版本，节点值可为负数。 - 相同值序列若对应不同节点路径，仍分别保留。
- 路径和用
64位整数累计。
题意分析
每条向下路径都是某条根到当前节点路径的一个连续后缀。当前前缀和减去某个祖先之前的前缀和，便得到该路径和；要枚举全部答案，哈希表必须保存前缀出现位置，不能只保存次数。
解法：前缀和记录起点并复制路径
核心思路
[!blue]
DFS 中
path保存当前根到节点的值，sum保存其 64 位和；starts[value]保存当前祖先链上该前缀和对应的全部路径长度。预置和为 0、长度为 0，覆盖从根开始的路径。进入节点后，所有前缀和为
sum-target的旧位置都是合法起点，复制path[start:]加入结果。必须先查询再登记当前前缀，避免target == 0时把当前位置之后的空路径计入。相同和值有多个位置时全部保留，对应不同节点路径。递归处理左右子树后，撤销当前前缀的最后一次登记并移除路径末项。这样哈希表只描述当前祖先链，不会把兄弟分支拼成不合法的向下路径；结果副本不会被回溯修改。
解题步骤
- DFS 保存当前路径和、节点路径，以及每个祖先前缀对应的路径长度。
- 查询 sum-target 的全部起点，复制对应后缀加入结果，再登记当前前缀。
- 处理孩子后撤销当前前缀与路径末项。
代码实现
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public List<List<Integer>> paths(TreeNode root, long target) {
List<List<Integer>> out = new ArrayList<>();
Map<Long, List<Integer>> starts = new HashMap<>();
starts.put(0L, new ArrayList<>(List.of(0)));
dfs(root, 0, target, new ArrayList<>(), starts, out);
return out;
}
private void dfs(
TreeNode node,
long sum,
long target,
List<Integer> path,
Map<Long, List<Integer>> starts,
List<List<Integer>> out) {
if (node == null) {
return;
}
sum += node.val;
path.add(node.val);
for (int start : starts.getOrDefault(sum - target, List.of())) {
out.add(new ArrayList<>(path.subList(start, path.size())));
}
starts.computeIfAbsent(sum, k -> new ArrayList<>()).add(path.size());
dfs(node.left, sum, target, path, starts, out);
dfs(node.right, sum, target, path, starts, out);
List<Integer> positions = starts.get(sum);
positions.remove(positions.size() - 1);
if (positions.isEmpty()) {
starts.remove(sum);
}
path.remove(path.size() - 1);
}
}
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func paths(root *TreeNode, target int64) [][]int {
out := [][]int{}
path := []int{}
starts := map[int64][]int{
0: {
0,
},
}
var dfs func(*TreeNode, int64)
dfs = func(node *TreeNode, sum int64) {
if node == nil {
return
}
sum += int64(node.Val)
path = append(path, node.Val)
for _, start := range starts[sum-target] {
out = append(out, append([]int(nil), path[start:]...))
}
starts[sum] = append(starts[sum], len(path))
dfs(node.Left, sum)
dfs(node.Right, sum)
starts[sum] = starts[sum][:len(starts[sum])-1]
if len(starts[sum]) == 0 {
delete(starts, sum)
}
path = path[:len(path)-1]
}
dfs(root, 0)
return out
}
复杂度分析
- 时间复杂度：期望 $O(n+R)$。
- 空间复杂度：辅助空间 $O(h)$，结果空间 $O(R)$；R 为所有输出路径的总节点数，h 为树高。
关键点总结
[!green]
一个前缀和值可能有多个起点，全部需要保留；计数题只存次数，枚举题必须保留位置。
易错点总结
[!yellow]
先查询再登记当前前缀，避免空路径；离开节点必须回退，不能混入兄弟分支。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 437. 路径总和 III | 中等 | 原题前缀和表只存次数，本题要输出路径，因此同一前缀和必须保存所有起点。 |
| 113. 路径总和 II | 中等 | 同样复制节点路径作为输出，原题仅允许根到叶，本题允许任意祖先到后代的路径。 |