leetcode173-二叉搜索树迭代器

原题

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

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

示例:

leetcode173-二叉搜索树迭代器

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

提示:

  • next() 和 hasNext() 操作的时间复杂度是 O(1),并使用 O(h) 内存,其中 h 是树的高度。
  • 你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 中至少存在一个下一个最小的数。

解法

思想

理解二叉搜索树的数据结构,像二叉树的中序遍历那样构造一个list。

代码

class BSTIterator {
    List<TreeNode> list;
    int cur;
    public BSTIterator(TreeNode root) {
        list = new ArrayList<>();
        cur = -1;
        buildList(root);
    }

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

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

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        if(cur<list.size()-1) return true;
        return false;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode173-%e4%ba%8c%e5%8f%89%e6%90%9c%e7%b4%a2%e6%a0%91%e8%bf%ad%e4%bb%a3%e5%99%a8/