Share my two C++ solutions,and I'm not sure if the second solution meets the requirements


  • 0
    V

    Solution(1):

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

    Solution(2):

    class BSTIterator {
    public:
        queue<TreeNode *> q;
        
        BSTIterator(TreeNode *root) {
            traversal(root);
        }
        
        void traversal(TreeNode *root) {
            if (root == NULL)
                return;
            
            
            if (root->left != NULL)
                traversal(root->left);
                
            q.push(root);
                
            if (root->right != NULL)
                traversal(root->right);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return !q.empty();
        }
    
        /** @return the next smallest number */
        int next() {
            int number = q.front()->val;
            q.pop();
            
            return number;
        }
    };

  • 0
    S

    second solution does not meet the memory requirement. You have O(N), where N being number of nodes. It requires O(h) which is the heigh of the tree. Or O(log n) space, since the tree is a search tree, it must be balance.


Log in to reply
 

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