欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++实现LeetCode(173.二叉搜索树迭代器)

程序员文章站 2022-03-23 23:52:06
[leetcode] 173.binary search tree iterator 二叉搜索树迭代器implement an iterator over a binary search tree (...

[leetcode] 173.binary search tree iterator 二叉搜索树迭代器

implement an iterator over a binary search tree (bst). your iterator will be initialized with the root node of a bst.

calling next() will return the next smallest number in the bst.

note: next() and hasnext() should run in average o(1) time and uses o(h) memory, where h is the height of the tree.

credits:
special thanks to  for adding this problem and creating all test cases.

这道题主要就是考二叉树的中序遍历的非递归形式,需要额外定义一个栈来辅助,二叉搜索树的建树规则就是左<根<右,用中序遍历即可从小到大取出所有节点。代码如下:

/**
 * definition for binary tree
 * struct treenode {
 *     int val;
 *     treenode *left;
 *     treenode *right;
 *     treenode(int x) : val(x), left(null), right(null) {}
 * };
 */
class bstiterator {
public:
    bstiterator(treenode *root) {
        while (root) {
            s.push(root);
            root = root->left;
        }
    }

    /** @return whether we have a next smallest number */
    bool hasnext() {
        return !s.empty();
    }

    /** @return the next smallest number */
    int next() {
        treenode *n = s.top();
        s.pop();
        int res = n->val;
        if (n->right) {
            n = n->right;
            while (n) {
                s.push(n);
                n = n->left;
            }
        }
        return res;
    }
private:
    stack<treenode*> s;
};

/**
 * your bstiterator will be called like this:
 * bstiterator i = bstiterator(root);
 * while (i.hasnext()) cout << i.next();
 */