难度简单1125
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。示例 2：
输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。示例 3：
输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。提示：
- 树中节点的数目在范围
[0, 5000]内 -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
1、递归法
这道题并不难，并且递归法中有两种不太一样的思路，我们这里都来列举一下：
第一种方法就很常规，我们定义一个 sum 变量，记录从根节点到叶子节点的整个路径的节点值的和，到了叶子节点之后，我们需要判断一下 sum 和 targetSum 是否相同即可，不相同的话则进行回溯，如果相同则直接剪枝（利用按位或来实现）！
class Solution {
public:
bool GetSum(TreeNode* root, int sum, int targetSum)
{
if(root == nullptr)
return false;
sum += root->val;
// 如果到了叶子节点，则判断是否相同
if(root->left == nullptr && root->right == nullptr)
{
if(sum == targetSum)
return true;
}
return GetSum(root->left, sum, targetSum) || GetSum(root->right, sum, targetSum);
}
bool hasPathSum(TreeNode* root, int targetSum) {
return GetSum(root, 0, targetSum);
}
}; 第二种方法有点逆向思维，我们不是要求大小和 targetSum 一样的路径吗，那么我们直接就拿 targetSum 每次去减掉路径上结点的值，直到遇到叶子节点，此时判断一下当前的 targetSum 是否已经减为 0 了，是的话则直接返回 true，不是的话则进行回溯判断其它路径！
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr)
return false;
targetSum -= root->val; // 注意这里是jia
// 如果到了叶子节点，则判断是否相同
if(root->left == nullptr && root->right == nullptr)
{
if(0 == targetSum)
return true;
}
return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);
}
};2、迭代法
其实不难，就是一个用栈来模拟递归遍历的过程，只不过要注意的是我们存放在栈中的元素不只是结点指针了，还得加上从根节点到当前节点的路径和，所以我们得使用 C++ 中的 pair<TreeNode, int>* 来存储！
其它步骤都是类似的，遇到叶子节点并且路径和已经与目标和相同时则直接返回 true，最后迭代完全部的结点之后，没有得到结果则直接返回 false！
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root == nullptr)
return false;
stack<pair<TreeNode*, int>> st;
st.push(make_pair(root, root->val));
while(!st.empty())
{
auto node = st.top();
st.pop();
// 如果到了叶子节点，则判断是否相同
if(node.first->left == nullptr && node.first->right == nullptr && node.second == targetSum)
return true;
// 记得入栈左右节点的时候，节点值需要加上之前的路径和也就是node.second
if(node.first->right != nullptr) // 先放入右节点
st.push(make_pair(node.first->right, node.first->right->val + node.second));
if(node.first->left != nullptr) // 再放入左节点
st.push(make_pair(node.first->left, node.first->left->val + node.second));
}
return false;
}
};