当前位置 博文首页 > 文章内容

    173. 二叉搜索树迭代器

    作者: 栏目:未分类 时间:2020-08-18 16:01:01

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    173. 二叉搜索树迭代器

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

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

    示例:

     

     

     

    BSTIterator iterator = new BSTIterator(root);

    iterator.next();    // 返回 3

    iterator.next();    // 返回 7

    iterator.hasNext(); // 返回 true

    iterator.next();    // 返回 9

    iterator.hasNext(); // 返回 true

    iterator.next();    // 返回 15

    iterator.hasNext(); // 返回 true

    iterator.next();    // 返回 20

    iterator.hasNext(); // 返回 false

     

    class BSTIterator {
    private:
        vector<TreeNode*> S;
    public:
        BSTIterator(TreeNode* root){
            while(root){
                S.push_back(root);
                root = root->left;
            }
        }
        int next() {
            TreeNode* t = S.back();
            S.pop_back();
            int val = t->val;
            t = t->right;
            while(t){
                S.push_back(t);
                t = t->left;
            }
            return val;
        }
        bool hasNext() {
            return !S.empty();
        }
    };

     

     

     

     

    173. 二叉搜索树迭代器