【文末福利】每日一道 LeetCode (26):路径总和
共 2217字,需浏览 5分钟
·
2020-08-22 16:55
❝每天 3 分钟,走上算法的逆袭之路。
❞
前文合集
代码仓库
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 queueNode = new LinkedList<>();
queueNode.offer(root);
Queue 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);
}
果然递归的代码要比迭代的代码简练很多。