173.二叉搜索树迭代器

题目描述

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // 返回 3
iterator.next();    // 返回 7
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 9
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 15
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 20
iterator.hasNext(); // 返回 false

题解

DFS + 列表

需要写一个构造器, 然后实现两个方法. 因为要输出的是下一个最小的节点, 所以很容易想到中序遍历, 然后一个一个输出.

大致思路为:

1. 写构造器, 当传入一个二叉搜索树时, 直接将其中序遍历, 并将结果用列表存放
2. 初始化一个变量, 时刻记录当前输出到哪里, 即再次调用next() 和hasNext() 时要查看的位置
3. 当调用next() , 指针移动一位, 当调用hasNext(), 指针不动

class BSTIterator {
    
    private int index = -1;
    List<Integer> list = new ArrayList<>();

    public BSTIterator(TreeNode root) {
        inOrder(root);
    }

    private void inOrder(TreeNode root) {
        if (root != null) {
            if (root.left != null)
                inOrder(root.left);
            list.add(root.val);
            if (root.right != null)
                inOrder(root.right);
        }
    }

    /**
     * @return the next smallest number
     */
    public int next() {
        return list.get(++index);
    }

    /**
     * @return whether we have a next smallest number
     */
    public boolean hasNext() {
        return index != list.size() - 1;
    }
}