树与图中等1 种解法

#113路径总和 II

返回所有节点值之和等于目标值的根到叶路径。

#二叉树#深度优先搜索#回溯

解题主线

共享路径容器需要在递归返回前撤销当前节点。

命中时复制路径，避免后续回溯修改已保存答案。

解法 1：局部状态回溯

方法内创建结果和路径，DFS 中执行选择、递归、撤销。

时间复杂度

O(n²) 最坏，复制每条路径的总成本可达 O(n²)

空间复杂度

O(h)，不计返回结果

113. 路径总和 II · 局部状态回溯

java

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.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);
    }
}

方法内创建结果和路径，DFS 中执行选择、递归、撤销。

边界与易错点

结果和路径不能作为不清空的实例字段，否则重复调用会产生状态污染。
只有叶子节点才能形成有效路径。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/tree/Q112_113_hasPathSum.java