【题目描述】
Design an iterator over a binary search tree with the following rules:
·Elements are visited in ascending order (i.e. an in-order traversal)
·next()andhasNext()queries run in O(1) time in average.
设计实现一个带有下列属性的二叉查找树的迭代器：
·元素按照递增的顺序被访问（比如中序遍历）
·next()和hasNext()的询问操作要求均摊时间复杂度是O(1)
【题目链接】
www.lintcode.com/en/problem/binary-search-tree-iterator/
【题目解析】
因为next()和hasnext()规定的时间复杂度为O(1)，而要求可以使用O(h)的memory.很容易想到用一个O(h)的stack来储存BST中的小数。
初始化时，需要将h个小数放入stack中，可以选取BST中最左边的子节点，共h个，栈顶元素为最小元素。每次next()取栈顶元素，并且将符合条件的值加入栈中。
【参考答案】
