LintCode领扣 题解丨谷歌秋招原题：二叉查找树迭代器

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

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

}
更多题解参考：九章算法官网