C++ solutions based on in-order-iterative methodology


  • 0
    M
    using namespace std;
    class BSTIterator {
    public:
        stack<TreeNode*> stnodes;
        BSTIterator(TreeNode *root) {
            findleft(root);
        }
    
        /** @return whether we have a next smallest number */
        bool hasNext() {
            return (stnodes.size()>0);
        }
        /** @return the next smallest number */
        int next() {
            auto smallnd = stnodes.top();
            stnodes.pop();
            if(smallnd->right) findleft(smallnd->right); //* important here. 
            return smallnd->val;
        }
        void findleft(TreeNode* root){
            while(root){
                stnodes.push(root);
                root = root->left;
            }
        }
    };
    

Log in to reply
 

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