LCR153二叉树中和为目标值的路径

题目来源：2024中金所秋招编程题
题目链接：https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/description/

小回说过，不要垂头丧气，即使失去一切，明天仍在你的手里。哪怕今天过的在不如意，我们也咬牙坚持坚持，在做一道力扣

题目描述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

题目示例

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

输入：root = [1,2,3], targetSum = 5
输出：[]

输入：root = [1,2], targetSum = 0
输出：[]

题目解析

1. 对于这类求和问题，还是从根节点到叶子节点的这种，有多种分支多个结果，我们就可以考虑使用递归+回溯的方式来解决
2. 用result来保存最后的答案，用path来保存中间过程中满足题意的答案；同时我们再判断条件的时候也要注意叶子节点的判断

题目答案

public class Solution {
    //示例方便debug
    public static void main(String[] args) {
        TreeNode root = new TreeNode(5);
        TreeNode node4 = new TreeNode(4);
        TreeNode node11 = new TreeNode(11);
        TreeNode node7 = new TreeNode(7);
        TreeNode node2 = new TreeNode(2);
        root.left=node4;
        node4.left=node11;
        node11.left=node7;
        node11.right=node2;

        new Solution().pathTarget(root,22);

    }

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    private int target;

    public List<List<Integer>> pathTarget(TreeNode root, int target) {
        this.target = target;
        travel(root, 0);
        return result;
    }

    private void travel(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        //中左右的遍历方式
        sum += root.val;
        path.add(root.val);
        if (sum == target && root.left == null && root.right == null) {
            result.add(new ArrayList<>(path));
        }
        //往左递归
        travel(root.left, sum);
        //往右递归
        travel(root.right, sum);
        //回溯
        path.remove(path.size() - 1);
    }
}

ps：这里sum再往右递归结束完了之后不需要再减，因为当一个递归结束之后的sum会回到上一层的状态