面试算法55：二叉搜索树迭代器

题目

请实现二叉搜索树的迭代器BSTIterator，它主要有如下3个函数。

• 构造函数：输入二叉搜索树的根节点初始化该迭代器。
• 函数next：返回二叉搜索树中下一个最小的节点的值。
• 函数hasNext：返回二叉搜索树是否还有下一个节点。

分析

如果对二叉树的中序遍历的迭代代码足够熟悉，我们就会注意到中序遍历的迭代代码中有一个while循环，循环的条件为true时循环体每执行一次就遍历二叉树的一个节点。当while循环的条件为false时，二叉树中的所有节点都已遍历完。因此，中序遍历的迭代代码中的while循环可以看成迭代器hasNext的判断条件，而while循环体内执行的操作就是函数next执行的操作。

解

public class BSTIterator {TreeNode cur;Stack<TreeNode> stack;public BSTIterator(TreeNode root) {cur = root;stack = new Stack<>();}public boolean hasNext() {return cur != null || !stack.isEmpty();}public int next() {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.pop();int val = cur.val;cur = cur.right;return val;}
}