Use Queue method c++ very easy


  • -1
    S

    class BSTIterator {

    public:

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

    };


  • 0
    P

    This requires memory that is linear in the number of nodes, not in the height of the tree.


Log in to reply
 

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