[数据结构与算法]LeetCode-113路径总和II-中等

标题：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

代码Java

public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        List<Integer> temp = new LinkedList<>();
        int target = targetSum;
        find(root, ans, temp, target);
        return ans;
    }
    public void find(TreeNode root, List<List<Integer>> ans, List<Integer> temp, int target) {
        temp.add(root.val);
        if (root.left == null && root.right == null) {
            int sum = 0;
            for (Integer x : temp) {
                sum += x;
            }
            if (sum == target) {

// res.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到res
// res.add(path)：将res尾部指向了path地址，后续path内容的变化会导致res的变化。

                ans.add(new ArrayList<>(temp));
            }
            return;
        }
        if (root.left != null) {
            find(root.left, ans, temp, target);
            temp.remove(temp.size() - 1);
        }
        if (root.right != null) {
            find(root.right, ans, temp, target);
            temp.remove(temp.size() - 1);
        }
    }



    public List<List<Integer>> pathSum1(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res; // 非空判断

        List<Integer> path = new LinkedList<>();
        preorderdfs(root, targetSum, res, path);
        return res;
    }

    public void preorderdfs(TreeNode root, int targetsum, List<List<Integer>> res, List<Integer> path) {
        path.add(root.val);
        // 遇到了叶子节点
        if (root.left == null && root.right == null) {
            // 找到了和为 targetsum 的路径
            if (targetsum - root.val == 0) {
                res.add(new ArrayList<>(path));
            }
            return; // 如果和不为 targetsum，返回
        }

        if (root.left != null) {
            preorderdfs(root.left, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
        if (root.right != null) {
            preorderdfs(root.right, targetsum - root.val, res, path);
            path.remove(path.size() - 1); // 回溯
        }
    }