本文共 1397 字，大约阅读时间需要 4 分钟。

1. 题目信息

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

BSTIterator iterator = new BSTIterator(root);iterator.next();    // 返回 3iterator.next();    // 返回 7iterator.hasNext(); // 返回 trueiterator.next();    // 返回 9iterator.hasNext(); // 返回 trueiterator.next();    // 返回 15iterator.hasNext(); // 返回 trueiterator.next();    // 返回 20iterator.hasNext(); // 返回 false

提示：

next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。

来源：力扣（LeetCode）

2. 二叉树中序遍历

• 搜索树中序是非降的
  

class BSTIterator {
       stack
   
     stk;    TreeNode *cur;public:    BSTIterator(TreeNode* root) {
           cur = root;    }        /** @return the next smallest number */    int next() {
           if(!hasNext())            return -1;        while(cur)        {
               stk.push(cur);            cur = cur->left;        }        cur = stk.top();        int v = cur->val;        stk.pop();        cur = cur->right;        return v;    }        /** @return whether we have a next smallest number */    bool hasNext() {
           return !stk.empty() || cur;    }};/** * Your BSTIterator object will be instantiated and called as such: * BSTIterator* obj = new BSTIterator(root); * int param_1 = obj->next(); * bool param_2 = obj->hasNext(); */
   

转载地址：https://michael.blog.csdn.net/article/details/100549417 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！