LeetCode_63_PathSumII

LeetCode

发布日期: 2022-06-01

更新日期: 2022-06-01

文章字数: 830

阅读时长: 4 分

阅读次数:

1. question: 路径总和 II（中等）

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-sum-ii

示例 1：

示例1

1 2	输入：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：

示例2

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

示例 3：

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

提示：

1
2
3

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

2. answers

这道题和前面那道题类似，区别在于，这道题需要找出所有的路径，并且输出的是路径。其实找所有路径不难，难点在于怎么保存路径。因为以递归的思路来看，只有到达叶子节点时，才能知道到底能否满足要求，但是高层的节点已经遍历完了，我们不知道应不应该保存。

实际上，递归是会逐层返回高层的，完全可以在递归的时候返回当前层满足条件的子路径。逐层扩充到高层即可。代码如下所示：

public class Solution_0062 {

    public static List<List<Integer>> getPath(TreeNode tn, Integer targetSum) {

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

        // 为了区分递归终止和root本来就是空树。
        // 这里在递归的时候，保证进来的不是空树。

        // 递归结束条件
        if(tn.left == null && tn.right == null) {
            if(targetSum - tn.val == 0) {

                List<Integer> temp = new ArrayList<>();
                temp.add(tn.val);
                result.add(temp);
            }

            return result;
        }

        // 递归未结束，则遍历左右子树，找出可能的路径。
        List<List<Integer>> left = new ArrayList<>();
        List<List<Integer>> right = new ArrayList<>();

        if(tn.left != null)
            left = getPath(tn.left, targetSum - tn.val);

        if(tn.right != null)
            right = getPath(tn.right, targetSum - tn.val);

        // 然后将当前节点加入到找到的路径中。注意，题目要求是从根节点到叶子节点的顺序。
        for(List<Integer> list: left) {

            List<Integer> temp = new ArrayList<>();

            // 先添加根节点
            temp.add(tn.val);
            temp.addAll(list);

            result.add(temp);
        }

        for(List<Integer> list: right) {

            List<Integer> temp = new ArrayList<>();

            // 先添加根节点
            temp.add(tn.val);
            temp.addAll(list);

            result.add(temp);
        }

        // 此时必定都不是null
        return result;
    }

    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {

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

        if(root == null) return result;

        result = getPath(root, targetSum);

        return result;

    }

    public static void main(String[] args) {

//        TreeNode tn10 = new TreeNode(1);
//        TreeNode tn9 = new TreeNode(5);
//        TreeNode tn8 = new TreeNode(2);
//        TreeNode tn7 = new TreeNode(7);
//        TreeNode tn6 = new TreeNode(4, tn9, tn10);
//        TreeNode tn5 = new TreeNode(13);
//        TreeNode tn4 = new TreeNode(11, tn7, tn8);
//        TreeNode tn3 = new TreeNode(8, tn5, tn6);
//        TreeNode tn2 = new TreeNode(4, tn4, null);
//        TreeNode tn1 = new TreeNode(5, tn2, tn3);
//
//        List<List<Integer>> result = pathSum(tn1, 22);


//        TreeNode tn3 = new TreeNode(3);
//        TreeNode tn2 = new TreeNode(2);
//        TreeNode tn1 = new TreeNode(1, tn2, tn3);
//
//        List<List<Integer>> result = pathSum(tn1, 4);

        List<List<Integer>> result = pathSum(null, 4);


        for(List<Integer> list: result) {
            for(Integer i: list)
                System.out.print(i + "\t");
            System.out.println();
        }
    }
}