non-recursion c++ solution


  • 0
    S

    bool isLeaf(TreeNode* node){
    return !node->right && !node->left;
    }
    bool hasPathSum(TreeNode* root, int sum) {
    if(!root) return false;
    if(!root->left && !root->right) return sum==root->val;
    int temp=sum;
    tuple<TreeNode*,int> nodesum;
    queue<tuple<TreeNode*,int>> q;
    if(root->left)
    q.push(tuple<TreeNode*,int>(root->left,sum-root->val));
    if(root->right)
    q.push(tuple<TreeNode*,int>(root->right,sum-root->val));
    while(!q.empty()){
    auto t1=q.front();
    TreeNode* tn1=get<0>(t1);
    int remain=get<1>(t1);
    q.pop();
    if(isLeaf(tn1)){
    if(remain==tn1->val) return true;
    }
    else{
    if(tn1->left)
    q.push(tuple<TreeNode*,int>(tn1->left,remain-tn1->val));
    if(tn1->right)
    q.push(tuple<TreeNode*,int>(tn1->right,remain-tn1->val));
    }
    }
    return false;
    }


Log in to reply
 

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