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.
题意：
实现二分搜索树的hasNext() 以及next() 操作，要求 O(1) time and O(h) memory。
思路：
暴力的方法是遍历整个树然后将所有元素放入有序的队列中，依次取出，但空间复杂度为O(n)。O(h)的复杂度的解法可通过一个栈来实现：依次将最左边的元素压栈，每次弹出最左下的元素即为最小的元素，同时判断其是否有右子树，若有右子树则继续将其右结点的左边元素依次压栈，循环直到栈为空。
C++：
/**
* 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):_min() {
while(root != )
{
_stack.push(root);
root = root->left;
}
} /** @return whether we have a next smallest number */
bool hasNext() { if(_stack.empty())
return false;
else
{
TreeNode* curNode = _stack.top();
_min = curNode->val;
_stack.pop(); if(curNode->right != )
{
TreeNode* newNode = curNode->right;
while(newNode != )
{
_stack.push(newNode);
newNode = newNode->left;
}
}
return true;
}
} /** @return the next smallest number */
int next() {
return _min;
} private:
stack<TreeNode*> _stack;
int _min;
}; /**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/
Python：
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None class BSTIterator:
# @param root, a binary search tree's root node
def __init__(self, root):
self.minval = 0
self.L = []
while root is not None:
self.L.append(root)
root = root.left # @return a boolean, whether we have a next smallest number
def hasNext(self):
if len(self.L) == 0:
return False
else:
curNode = self.L.pop()
self.minval = curNode.val if curNode.right is not None:
newNode = curNode.right
while newNode is not None:
self.L.append(newNode)
newNode = newNode.left return True # @return an integer, the next smallest number
def next(self):
return self.minval # Your BSTIterator will be called like this:
# i, v = BSTIterator(root), []
# while i.hasNext(): v.append(i.next())