A short and fastest solution in C++


  • -2
    I

    In order to solve the problem we need to have a in-order traversal on the tree so that we can return the smallest val and then the second smallest, the third smallest...
    We can implement in-order traversal in a recursive way, but using stack we can write a better one. First of all, push the root, root->left, root->left->left, .... into the stack. For each time we pop a node, just check its right child, if it has a right child, push the right-child, right-child->left, right-child->left->left, .... Similar idea to
    ChuntaoLu, pavel-shlyk and scott's.

    class BSTIterator {
    public:
        BSTIterator(TreeNode *root) {
            sta = stack<TreeNode*>();
            for(TreeNode *cur=root; cur; cur=cur->left) {
                sta.push(cur);
            }
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !sta.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode *cur = sta.top();
            sta.pop();
            for(TreeNode *i=cur->right; i; i=i->left) {
                sta.push(i);
            }
            return cur->val;
        }
    private:
        stack<TreeNode*> sta;
    };

Log in to reply
 

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