LeetCode_62_PathSum

LeetCode

发布日期: 2022-06-01

更新日期: 2022-06-01

文章字数: 956

阅读时长: 4 分

阅读次数:

1. question: 路径总和（简单）

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

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

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

示例 1：

示例1

1
2
3

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

示例2

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

1
2
3

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

提示：

1
2
3

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

2. answers

这道题最开始的想法就是遍历所有路径，保存路径和，最后比较是否与目标值相同。遍历采用递归的方式，即以当前节点为根的二叉树，其全部路径等于，以当前节点的左右子节点为根节点的二叉树的全部路径加上左右子节点。

代码如下所示：

public class Solution_0061 {

    public static List<Integer> getSum(TreeNode tn) {

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

        if(tn == null) return result;

        // 分别计算左右节点的全路径。
        List<Integer> leftResult = getSum(tn.left);
        List<Integer> rightResult = getSum(tn.right);

        // 如果是叶子节点，则将自身加入到结果中
        if(leftResult.size() == 0 && rightResult.size() == 0)
            result.add(tn.val);
        else {
            // 如果不是叶子节点，则遍历左右子树，更新路径和。

            for(Integer i: leftResult)
                result.add(i + tn.val);

            for(Integer i: rightResult)
                result.add(i + tn.val);
        }


        return result;
    }

    public static boolean hasPathSum(TreeNode root, int targetSum) {

        // 获取全部路径和
        List<Integer> result = getSum(root);

        // 判断是否满足条件
        for(Integer i: result)
            if(targetSum == i) return true;

        return false;
    }

    public static void main(String[] args) {


//        TreeNode tn9 = new TreeNode(1);
//        TreeNode tn8 = new TreeNode(2);
//        TreeNode tn7 = new TreeNode(7);
//        TreeNode tn6 = new TreeNode(4, null, tn9);
//        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);
//
//        System.out.println(hasPathSum(tn1, 22));


//        TreeNode tn3 = new TreeNode(3);
//        TreeNode tn2 = new TreeNode(2);
//        TreeNode tn1 = new TreeNode(1, tn2, tn3);
//
//        System.out.println(hasPathSum(tn1, 3));

        System.out.println(hasPathSum(null, 3));
    }
}

参考了题解，其实在遍历的时候，没必要开辟空间保留路径和。路径和课可以看成是节点之和，也可以看成是目标值逐个减去节点值，最后到叶子节点时，目标值为0。本质上在递归的时候，将目标值减去根节点的值，作为新的目标值即可。代码如下所示：

public class Solution_0061_02 {

    public static boolean hasPathSum(TreeNode root, int targetSum) {

        // 为了区分递归终止和root本来就是空树。
        // 这里在递归的时候，保证进来的不是空树。
        if(root == null) return false;

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

        Boolean left = null;
        Boolean right = null;

        if(root.left != null)
            left = hasPathSum(root.left, targetSum - root.val);

        if(root.right != null)
            right = hasPathSum(root.right, targetSum - root.val);

        // 此时至少有一个不是null
        if(left == null) return right;
        if(right == null) return left;

        // 此时必定都不是null
        return left || right;
    }

    public static void main(String[] args) {
//        System.out.println(null || false);
        TreeNode tn3 = new TreeNode(3);
        TreeNode tn2 = new TreeNode(2);
        TreeNode tn1 = new TreeNode(1, tn2, tn3);

        System.out.println(hasPathSum(tn1, 0));
    }
}