class Solution {
public:
    bool traverse(TreeNode* root, int targetSum, int currentSum) {
        if(root == nullptr) return false;
        currentSum += root->val;

        if(root->left == nullptr && root->right == nullptr) {
            return currentSum == targetSum;
        }
        
        return traverse(root->left, targetSum, currentSum) || traverse(root->right, targetSum, currentSum);
    }
     
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        return traverse(root, targetSum, 0);
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        
        stack<pair<TreeNode*, int>> sta;
        sta.push(make_pair(root, root->val));

        while(!sta.empty()) {
            auto node = sta.top();
            sta.pop();

            if(node.first->left == nullptr && node.first->right == nullptr && targetSum == node.second) return true;

            if(node.first->right != nullptr) {
                sta.push(make_pair(node.first->right, node.second + node.first->right->val));
            }

            if(node.first->left != nullptr) {
                sta.push(make_pair(node.first->left, node.second + node.first->left->val));
            }
        }
        return false;
    }
};

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == nullptr) return false;
        
        queue<pair<TreeNode*, int>> que;
        que.push(make_pair(root, root->val));

        while(!que.empty()) {
            auto node = que.front();
            que.pop();
            
            if(node.first->left == nullptr && node.first->right == nullptr && node.second == targetSum) return true;
            if(node.first->left != nullptr) {
                que.push(make_pair(node.first->left, node.second + node.first->left->val));
            }
            if(node.first->right != nullptr) {
                que.push(make_pair(node.first->right, node.second + node.first->right->val));
            }
        }
        return false;
    }
};