23ms C++ solution using stack< pair<TreeNode*,bool> >


  • 0
    A
    class BSTIterator {
    protected:
        stack< pair<TreeNode*,bool> > s;
    public:
        BSTIterator(TreeNode *root) {
            checkin(root);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return (!s.empty());
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode *curr = s.top().first;
            bool booked = s.top().second;
            s.pop();
    
            if (booked) {
                checkin(curr);
                return next();
            } else {
                return curr->val;
            }
        }
    
        void checkin(TreeNode *curr) {
            while (curr) {
                if (curr->right) {
                    s.push(make_pair(curr->right, true));
                }
                s.push(make_pair(curr, false));
                curr = curr->left;
            }
        }
    };
    

Log in to reply
 

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