给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
class Solution {
private:
bool dfs_find(TreeNode* cur,int sum,int targetSum)
{
if(cur->left==nullptr&&cur->right==nullptr)
{
if(sum == targetSum) return true;
else return false;
}
bool l,r;
l = r = false;
if(cur->left) l = dfs_find(cur->left,sum + cur->left->val,targetSum);
if(cur->right) r = dfs_find(cur->right,sum + cur->right->val,targetSum);
return l|r;
}
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if(root==nullptr) return false;
bool res = dfs_find(root,root->val,targetSum);
return res;
}
bool haspathsum1(TreeNode* root, int sum) {
if (root == nullptr) return false;
// 此时栈里要放的是pair<节点指针，路径数值>
stack<std::pair<TreeNode*, int>> st;
st.push(std::pair<TreeNode*, int>(root, root->val));
while (!st.empty()) {
std::pair<TreeNode*, int> node = st.top();
st.pop();
// 如果该节点是叶子节点了，同时该节点的路径数值等于sum，那么就返回true
if (!node.first->left && !node.first->right && sum == node.second) return true;
// 右节点，压进去一个节点的时候，将该节点的路径数值也记录下来
if (node.first->right) {
st.push(std::pair<TreeNode*, int>(node.first->right, node.second + node.first->right->val));
}
// 左节点，压进去一个节点的时候，将该节点的路径数值也记录下来
if (node.first->left) {
st.push(std::pair<TreeNode*, int>(node.first->left, node.second + node.first->left->val));
}
}
return false;
}
};