LeetCode -- 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.
就是實現一個搜索二叉樹的迭代器。
思路：
初始化時對樹中序遍歷元素入隊列；hasNext：判斷隊列是否空；Next:拿出隊列當前元素。
缺陷：這個做法的缺陷在於如果只拿1個元素，仍然需要對整樹遍歷一次；可是大多數情況下，使用迭代器的目的顯然是從頭遍歷到尾，因此這個方案是make sense的。
實現代碼：
/**
* Definition for binary tree
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int x) { val = x; }
* }
*/
public class BSTIterator {
private Queue _values ;
public BSTIterator(TreeNode root)
{
_values = new Queue();
Init(root);
}
private void Init(TreeNode current)
{
if(current == null)
{
return;
}
Init(current.left);
_values.Enqueue(current.val);
Init(current.right);
}
/** @return whether we have a next smallest number */
public bool HasNext() {
return _values.Count > 0;
}
/** @return the next smallest number */
public int Next() {
var v = _values.Dequeue();
return v;
}
}
/**
* Your BSTIterator will be called like this:
* BSTIterator i = new BSTIterator(root);
* while (i.HasNext()) v[f()] = i.Next();
*/
