树与图中等1 种解法
#113路径总和 II
返回所有节点值之和等于目标值的根到叶路径。
#二叉树#深度优先搜索#回溯
原题
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 输出：[[5,4,11,2],[5,8,4,5]]
示例 2：
输入：root = [1,2,3], targetSum = 5 输出：[]
示例 3：
输入：root = [1,2], targetSum = 0 输出：[]
提示：
- 树中节点总数在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
解题主线
- 共享路径容器需要在递归返回前撤销当前节点。
- 命中时复制路径，避免后续回溯修改已保存答案。
解法 1：局部状态回溯
方法内创建结果和路径，DFS 中执行选择、递归、撤销。
-
时间复杂度： O(n²) 最坏，复制每条路径的总成本可达 O(n²)
-
空间复杂度： O(h)，不计返回结果
import java.util.*;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
backtrack(root, targetSum, new ArrayList<>(), result);
return result;
}
private void backtrack(TreeNode node, long remaining, List<Integer> path,
List<List<Integer>> result) {
if (node == null) return;
// path 与 remaining 始终描述从根到当前节点的选择状态。
path.add(node.val);
remaining -= node.val;
// 只有根到叶的完整路径才允许加入答案。
if (node.left == null && node.right == null && remaining == 0) {
// 保存副本，隔离后续回溯对共享路径的修改。
result.add(new ArrayList<>(path));
} else {
backtrack(node.left, remaining, path, result);
backtrack(node.right, remaining, path, result);
}
// 撤销当前选择，恢复父调用进入时的路径。
path.remove(path.size() - 1);
}
}边界与易错点
- 结果和路径不能作为不清空的实例字段，否则重复调用会产生状态污染。
- 只有叶子节点才能形成有效路径。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/tree/Q112_113_hasPathSum.java