【文末福利】每日一道 LeetCode (26)：路径总和
❝每天 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);
}
果然递归的代码要比迭代的代码简练很多。
