LeetCode173-二叉搜索树迭代器

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/binary-search-tree-iterator/

中文链接：https://leetcode-cn.com/problems/binary-search-tree-iterator/

题目详述

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

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

示例：

img

1
2
3
4
5
6
7
8
9
10
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 中至少存在一个下一个最小的数。

题目详解

由于给定的是一颗二叉搜索树，对它进行中序遍历得到的结果就是从小到大排列的。类似于 LeetCode94-二叉树的中序遍历，可以按照中序遍历的方式，一步一步进行迭代，这样可以不断得到下一个最小的数。

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
27
28
29
public class LeetCode_00173 {

    class BSTIterator {
        private Stack<TreeNode> stack;
        private TreeNode root;

        public BSTIterator(TreeNode root) {
            this.stack = new Stack<>();
            this.root = root;
        }

        /** @return the next smallest number */
        public int next() {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            int res = root.val;
            root = root.right;
            return res;
        }

        /** @return whether we have a next smallest number */
        public boolean hasNext() {
            return !stack.isEmpty() || root != null;
        }
    }
}