# 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
叶子节点 是指没有子节点的节点。
示例 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
示例 3：
输入：root = [1,2], targetSum = 0
输出：false
提示：
- 树中节点的数目在范围
[0, 5000] 内
-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
```
### after
```cpp
```
## 答案
```cpp
其他三个都是错的
```
## 选项
### A
```cpp
class Solution
{
public:
bool hasPathSum(TreeNode *root, int sum)
{
if (root == NULL)
{
return false;
}
vector node_stack;
vector sum_stack;
node_stack.push_back(root);
sum_stack.push_back(sum - root->val);
TreeNode *node;
int curr_sum;
while (!node_stack.empty())
{
node = node_stack.back();
node_stack.pop_back();
curr_sum = sum_stack.back();
sum_stack.pop_back();
if ((node->right == NULL) && (node->left == NULL) && (curr_sum == 0))
{
return true;
}
if (node->right != NULL)
{
node_stack.push_back(node->right);
sum_stack.push_back(curr_sum - node->right->val);
}
if (node->left != NULL)
{
node_stack.push_back(node->left);
sum_stack.push_back(curr_sum - node->left->val);
}
}
return false;
}
};
```
### B
```cpp
class Solution
{
public:
bool hasPathSum(TreeNode *root, int sum)
{
if (root == NULL)
return false;
stack> s;
s.push(make_pair(root, sum));
TreeNode *node = root;
int currSum;
while (!s.empty())
{
node = s.top().first;
currSum = s.top().second;
s.pop();
if (node->left == NULL && node->right == NULL && node->val == currSum)
return true;
if (node->right)
s.push(make_pair(node->right, currSum - node->val));
if (node->left)
s.push(make_pair(node->left, currSum - node->val));
}
return false;
}
};
```
### C
```cpp
class Solution
{
public:
bool hasPathSum(TreeNode *root, int sum)
{
if (!root)
return false;
if (!root->left && !root->right && root->val == sum)
return true;
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};
```