173.二叉搜索树迭代器

链接：173.二叉搜索树迭代器
难度：Medium
标签：栈、树、设计、二叉搜索树、二叉树、迭代器
简介：实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

题解 1 - typescript

• 编辑时间：2021-03-28
• 执行用时：144ms
• 内存消耗：49.6MB
• 编程语言：typescript
• 解法介绍：中序遍历存入数组。

class BSTIterator {
  private arr: number[] = [];
  constructor(root: TreeNode | null) {
    this.inorder(root);
  }
  next(): number {
    return this.arr.shift()!;
  }
  hasNext(): boolean {
    return this.arr.length > 0;
  }
  private inorder(node: TreeNode | null): void {
    if (node === null) return;
    this.inorder(node.left);
    this.arr.push(node.val);
    this.inorder(node.right);
  }
}

题解 2 - java

• 编辑时间：2020-02-24
• 执行用时：30ms
• 内存消耗：44.8MB
• 编程语言：java
• 解法介绍：中序遍历后储存到队列里。

class BSTIterator {
    Queue<Integer> queue = new LinkedList<Integer>();
    public BSTIterator(TreeNode root) {
        if(root!=null)
        inorder(root);
    }
    public int next() {
        return queue.poll();
    }
    public boolean hasNext() {
        return !queue.isEmpty();
    }
    public void inorder(TreeNode node) {
        if (node.left != null)
            inorder(node.left);
            queue.add(node.val);
        if (node.right != null)
            inorder(node.right);
    }
}