class BSTIterator {
private:
stack<TreeNode*> st;
public:
BSTIterator(TreeNode *root) {
find_left(root);
}
/** @return whether we have a next smallest number */
bool hasNext() {
if (st.empty())
return false;
return true;
}
/** @return the next smallest number */
int next() {
TreeNode* top = st.top();
st.pop();
if (top>right != NULL)
find_left(top>right);
return top>val;
}
/** put all the left child() of root */
void find_left(TreeNode* root)
{
TreeNode* p = root;
while (p != NULL)
{
st.push(p);
p = p>left;
}
}
};
My Solution in C++, in average O(1) time and uses O(h) memory


@dequn when you traverse the tree using this next(), each edge of the tree has been visited at most twice, once cause' next(), once cause' find_left(). The whole edges of a tree is
n1
, supposed ann
node tree.
So average time of next() is2n / n = 2
, average time is O(1).