Easy C++ solution using height concept of tree


  • 0
    P

    class Solution {
    public:
    bool hasPathSum(TreeNode* root, int sum) {
    queue<TreeNode*> q;
    vector<int> v;
    if(root==NULL)
    return false;
    q.push(root);
    TreeNode* node;
    int i=0;
    v.push_back(root->val);
    while(!q.empty())
    {
    int cnt=q.size();
    while(cnt--)
    {
    node=q.front();
    if(node->left)
    {
    q.push(node->left);
    v.push_back(node->left->val+v[i]);
    }
    if(node->right)
    {
    q.push(node->right);
    v.push_back(node->right->val+v[i]);
    }
    if(node->left!=NULL||node->right!=NULL)
    v.erase(v.begin()+i);
    else
    i++;
    q.pop();
    }
    }
    for(int i=0;i<v.size();i++)
    if(v[i]==sum)
    return true;
    return false;
    }
    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.