Short C++ O(n) / O(h) space solutions


  • 0

    Solution 1. O(n) space.

    class BSTIterator {
    public:
        BSTIterator(TreeNode *root) {
            load(s, root);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !s.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            int n = s.top();
            s.pop();
            return n;
        }
        
    private:
        stack<int>s;
        
        void load(stack<int>& s, TreeNode* root){
            if(!root) return;
            load(s, root->right);
            s.push(root->val);
            load(s, root->left);
        }
    };
    

    Solution 2. O(h) space.

    class BSTIterator {
    public:
        BSTIterator(TreeNode *root) {
            load(s, root);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !s.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            TreeNode* node = s.top();
            s.pop();
            if(node->right) load(s, node->right);
            return node->val;
        }
        
    private:
        stack<TreeNode*>s;
        
        void load(stack<TreeNode*>& s, TreeNode* root){
            if(!root) return;
            s.push(root);
            load(s, root->left);
        }
    };
    

Log in to reply
 

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