设计实现一个带有下列属性的二叉查找树的迭代器：
next()返回BST中下一个最小的元素
元素按照递增的顺序被访问（比如中序遍历）
next()和hasNext()的询问操作要求均摊时间复杂度是O(1)
在线评测地址：LintCode 领扣
样例 1:
输入：{10,1,11,#,6,#,12}
输出：[1, 6, 10, 11, 12]
解释：
二叉查找树如下 :
10
/\
1 11
\
6 12
可以返回二叉查找树的中序遍历 [1, 6, 10, 11, 12]
样例 2:
输入：{2,1,3}
输出：[1,2,3]
解释：
二叉查找树如下 :
2
/ \
1 3
可以返回二叉查找树的中序遍历 [1,2,3]
【题解】
这是一个非常通用的利用 stack 进行 Binary Tree Iterator 的写法。
stack 中保存一路走到当前节点的所有节点，stack.peek() 一直指向 iterator 指向的当前节点。 因此判断有没有下一个，只需要判断 stack 是否为空 获得下一个值，只需要返回 stack.peek() 的值，并将 stack 进行相应的变化，挪到下一个点。
挪到下一个点的算法如下：
如果当前点存在右子树，那么就是右子树中“一路向西”最左边的那个点
如果当前点不存在右子树，则是走到当前点的路径中，第一个左拐的点
访问所有节点用时O(n)，所以均摊下来访问每个节点的时间复杂度时O(1)
public class BSTIterator {
private Stack<TreeNode> stack = new Stack<>();
// @param root: The root of binary tree.
public BSTIterator(TreeNode root) {
while (root != null) {
stack.push(root);
root = root.left;
}
}
//@return: True if there has next node, or false
public boolean hasNext() {
return !stack.isEmpty();
}
//@return: return next node
public TreeNode next() {
TreeNode curt = stack.peek();
TreeNode node = curt;
// move to the next node
if (node.right == null) {
node = stack.pop();
while (!stack.isEmpty() && stack.peek().right == node) {
node = stack.pop();
}
} else {
node = node.right;
while (node != null) {
stack.push(node);
node = node.left;
}
}
return curt;
}}
更多题解参考：九章算法官网
