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

[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();
 */