通关剑指 Offer——剑指 Offer II 055. 二叉搜索树迭代器

1.题目描述

剑指 Offer II 055. 二叉搜索树迭代器

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

示例：

输入
inputs = ["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
inputs = [[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False

2.解题思路与代码

2.1 解题思路

编写一个二叉搜索树的迭代器，使迭代器按照从小到大的顺序返回节点值。我们知道二叉搜索树的中序遍历得到的结果就是从小到大以此递增的，可以利用这一特性来完成题目。首先我们构建一个列表 list 存放二叉搜索树中序遍历经过的节点，然后在构造方法中对该二叉搜索树进行中序遍历，并放入列表 list 中。

List<TreeNode> list;
int index = -1;

public BSTIterator(TreeNode root) {
  list = new ArrayList<>();
  process(root);
}

public void process(TreeNode node) {
  if (node == null) {
    return;
  }
  process(node.left);
  list.add(node);
  process(node.right);
}

这里还需要一个 index 变量来遍历该列表，以模拟迭代器。我们需要完成迭代器的 next() 和 hasNext() 两个方法，next() 方法要获取 index 角标的下一位元素，即 list.get(++index)，而 hasNext 方法直接判断 index+1 是否小于列表长度即可。

public int next() {
  return list.get(++index).val;
}

public boolean hasNext() {
  return index + 1 < list.size();
}

2.2 代码

class BSTIterator {

    List<TreeNode> list;
    int index = -1;

    public BSTIterator(TreeNode root) {
        list = new ArrayList<>();
        process(root);
    }

    public void process(TreeNode node) {
        if (node == null) {
            return;
        }
        process(node.left);
        list.add(node);
        process(node.right);
    }

    public int next() {
        return list.get(++index).val;
    }

    public boolean hasNext() {
        return index + 1 < list.size();
    }
}

2.3 测试结果

通过测试

3.总结

• 利用二叉搜索树中序遍历结果是增序特性解答
• 也可以直接使用列表的迭代器解答