113. 路径总和 II

// 二叉树节点定义
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    // 存储所有满足条件的路径
    List<List<Integer>> res = new LinkedList<>();
    // 存储当前路径
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        // 调用回溯函数
        backtrack(root, targetSum);
        return res;
    }

    // 回溯函数
    private void backtrack(TreeNode root, int targetSum) {
        // 如果节点为空，直接返回
        if (root == null) return;

        // 将当前节点值加入路径
        path.add(root.val);
        // 目标值减去当前节点值
        targetSum -= root.val;

        // 如果当前是叶子节点且路径和等于目标值
        if (targetSum == 0 && root.left == null && root.right == null) {
            // 将当前路径的副本加入结果集
            res.add(new LinkedList<Integer>(path));
        }

        // 递归遍历左子树
        backtrack(root.left, targetSum);
        // 递归遍历右子树
        backtrack(root.right, targetSum);

        // 回溯：移除当前节点值
        path.removeLast();
    }
}