Could I get a better iterative method than this?


  • 0
    D

    I use two stacks: one record the node pointer, another record the sum from root to current node
    Then I iterate the tree using preorder

    bool hasPathSum(TreeNode *root, int sum) {
        if(root==NULL)
           return false;
        stack<TreeNode *> stk;
        stack<int> rec;
        stk.push(root);
        rec.push(root->val);
        while(!stk.empty())
        {
            TreeNode* cur=stk.top();
            int v=rec.top();
            rec.pop();
            stk.pop();
            if(cur->right)
            {
                stk.push(cur->right);
                rec.push(v+cur->right->val);
            }
            if(cur->left)
            {
                stk.push(cur->left);
                rec.push(v+cur->left->val);
            }
            if(!cur->left&&!cur->right)
            {
                if(v==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.