Easy understand c++ with stack


  • 0
    S

    stack st will always has the nextSmallest number on top of the stack.

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

Log in to reply
 

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