My c++ 24ms solution without stack


  • 0
    Z

    class BSTIterator {
    public:
    TreeNode *head;
    BSTIterator(TreeNode *root) {
    head=root;
    }

    /** @return whether we have a next smallest number */
    bool hasNext() {
        if(!head)
            return false;
        return true;
    }
    
    /** @return the next smallest number */
    int next() {
        TreeNode *cur=head;
        TreeNode *pre=NULL;
        while(cur->left){
            pre=cur;
            cur=cur->left;
        }
        int tmp= cur->val;
        if(pre)
            pre->left=cur->right;
        else
            head=cur->right;
        return tmp;
    }
    

    };


  • 0

    @zzzzbryant idea not bad, just not satisfied O(1) time, space is saved though


Log in to reply
 

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