面试算法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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26