[leetcode/lintcode 题解] 谷歌面试题：二叉查找树迭代器

设计实现一个带有下列属性的二叉查找树的迭代器：

next()返回 BST 中下一个最小的元素

元素按照递增的顺序被访问（比如中序遍历）
next()和 hasNext()的询问操作要求均摊时间复杂度是 O(1)

在线评测地址：

https://www.lintcode.com/problem/binary-search-tree-iterator/?utm_source=sc-zhihu-fks

样例 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;
    }
}