[stack] C++ O(1) time O(h) space with explanation


  • 0

    Push the left tree to stack, after traverse the left tree, push the right tree to stack.
    Memmory: O(h)
    Since there is only one hasNext() has to push the right tree to stack, the overall time complexity is O(n/n)=O(1).

    class BSTIterator {
        stack<int>s;
        bool twice=false;
        TreeNode* root;
    public:
        BSTIterator(TreeNode *root): root(root) {
            if(root) traversal(root->left);
        }
        
        void traversal(TreeNode* root){
            if(!root) return;
            if(root->right) traversal(root->right);
            s.push(root->val);
            if(root->left) traversal(root->left);
            return;
        }
        
        bool hasNext() {
            if(!root||(s.empty()&&twice)) return false;
            if(s.empty()&&twice==false){
                traversal(root->right); 
                s.push(root->val);
                twice=true;
            }
            return true;
        }
    
        int next() {
            int n=s.top();
            s.pop();
            return n;
        }
    };
    

Log in to reply
 

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