# 173. Binary Search Tree Iterator---这是一个类的设计题值得好好推敲

2017-01-13 10:44:55来源:网络收集作者:三线码农人点击

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 @ts for adding this problem and creating all test cases.

class BSTIterator {
stack myStack;
public:
BSTIterator(TreeNode *root) {
pushAll(root);
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !myStack.empty();
}
/** @return the next smallest number */
int next() {
TreeNode *tmpNode = myStack.top();
myStack.pop();
pushAll(tmpNode->right);
return tmpNode->val;
}
private:
void pushAll(TreeNode *node) {
for (; node != NULL; myStack.push(node), node = node->left);
}
};

class BSTIterator {
private:
stack 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);
}
/** put all the left child() of root */
void find_left(TreeNode* root)
{
TreeNode* p = root;
while (p != NULL)
{
st.push(p);
p = p->left;
}
}
};

class BSTIterator {
private:
stack sta;
public:
BSTIterator(TreeNode *root) {
findLeft(root);
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !sta.empty();
}
/** @return the next smallest number */
int next() {
TreeNode *top = sta.top();
sta.pop();
if(top->right != NULL)
findLeft(top->right);
}
/** put all the left child() of root */
void findLeft(TreeNode *node)
{
while(node!=NULL)
{
sta.push(node);
node = node->left;
}
}
};