My Solution in C++. Easy understanding.


  • 0
    N

    Using recursive inorder traversal.

    class BSTIterator {
    public:
    	BSTIterator(TreeNode *root) {
    		m_root = root;
    		cnt = 0;
    		inorderTraversal(m_root);
    	}
    
    	/** @return whether we have a next smallest number */
    	bool hasNext() {
    		return cnt < m_inorder.size() ? true : false;
    	}
    
    	/** @return the next smallest number */
    	int next() {
    		if (!hasNext()) return 0;
    		return m_inorder[cnt++];
    	}
    private:
    	TreeNode* m_root;
    	vector<int> m_inorder;
    	int cnt;
    
    	void inorderTraversal(TreeNode* root) {
    		if (root == nullptr) return;
    		inorderTraversal(root->left);
    		m_inorder.push_back(root->val);
    		inorderTraversal(root->right);
    	}
    };
    

Log in to reply
 

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