1. 首页
  2. LeetCode

每日一道 LeetCode (26):路径总和

每日一道 LeetCode (26):路径总和

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub: https://github.com/meteor1993/LeetCode

Gitee: https://gitee.com/inwsy/LeetCode

题目:路径总和

题目来源:https://leetcode-cn.com/problems/path-sum/

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树,以及目标和 sum = 22 。

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2 。

解题方案

今天这道题,咳咳,我终于会做了,可以嘚瑟一下了。

这道题我最开始几次解错了,没看清题的下场,题目里面说的很明确的两点,第一点是从根节点开始,到叶子节点结束,第二个点是叶子节点是指没有子节点的节点。

就是从跟到最后,寻找一条路径,看看有没有路径上的数字加起来和目标数字是一样的。

不知道各位看了有啥想法,反正我第一个想法就是迭代呗,全都循环出来,一层一层的做计算,看看迭代到最后有没有结果和目标一致。

解题方案一:迭代

直接放代码吧,这个看了代码基本上也就明白了:

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) return false;

    Queue<TreeNode> queueNode = new LinkedList<>();
    queueNode.offer(root);

    Queue<Integer> queueInts = new LinkedList<> ();
    queueInts.offer(root.val);

    while (!queueNode.isEmpty()) {
        TreeNode node = queueNode.poll();
        int temp = queueInts.poll();
        if (node.left == null && node.right == null) {
            if (temp == sum) {
                return true;
            }
        }

        if (node.left != null) {
            queueNode.offer(node.left);
            queueInts.offer(temp + node.left.val);
        }

        if (node.right != null) {
            queueNode.offer(node.right);
            queueInts.offer(temp + node.right.val);
        }
    }
    return false;
}

这段代码应该很好理解,我定义了两个队列,一个队列用来放当前的节点,另一个队列用来放从根节点到当前节点的和,在循环中,唯一会返回 true 的地方做了两个判断,一个是判断当前是叶子节点(左右节点都为 null ),还有一个是当前从队列中取出来的值和目标值相等。

解题方案二:递归

上面是用了迭代的方案,既然是二叉树,那么是不是还能用递归来解?

当然可以,但是我不会写,下面这段代码是在官方的答案中找出来的。

不禁为自己的智商感到捉急,看到答案能看懂,但是自己写就是写不出来。

public boolean hasPathSum_1(TreeNode root, int sum) {
    if (root == null) {
        return false;
    }
    if (root.left == null && root.right == null) {
        return sum == root.val;
    }
    return hasPathSum_1(root.left, sum - root.val) || hasPathSum_1(root.right, sum - root.val);
}

果然递归的代码要比迭代的代码简练很多。

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code