当前位置：首页 > article >正文

Leetcode 二叉搜索树迭代器

article 2025/3/6 0:51:34

在这里插入图片描述

通俗地解释这道题目的要求

这道题目要求你设计一个二叉搜索树（BST）的迭代器，让你能够像遍历一个数组那样，依次获取 BST 中的元素，并且始终按照 从小到大（中序遍历：左 -> 根 -> 右） 的顺序返回数据。

你需要实现：

BSTIterator(TreeNode root)：构造函数，接收 BST 的根节点，并初始化迭代器。
int next()：返回 BST 中下一个最小的元素（即按中序遍历顺序）。
boolean hasNext()：判断 BST 是否还有下一个元素可用。

简单理解：这个迭代器就像一本书的书签

BSTIterator 代表你正在阅读这本“BST 书”。
next() 就像翻页，每次都会给你下一个最小的值。
hasNext() 让你知道书里是否还有内容可以读。

举个例子

假设给你这样一棵 BST：

如果我们直接做中序遍历（左 -> 根 -> 右），顺序应该是：

3 → 7 → 9 → 15 → 20

你的 BSTIterator 需要实现：

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

换句话说，你需要实现一个数据结构，它能像“顺序访问数组”那样，从 BST 里按顺序取出数值。

和一般的 BST 遍历有啥区别？

通常，我们用递归（dfs(root.left); print(root.val); dfs(root.right);）来做中序遍历。但这样一次性就遍历完整棵树，不适用于只想一步步获取值的情况。

这个迭代器的核心目标：
✅ 不用一次性遍历完整棵树，而是按需取值
✅ next() 只返回当前的最小值，不会提前访问其他值
✅ hasNext() 只是检查还有没有值，而不会真正访问数据

这样，你可以像读小说一样一页一页地访问 BST，而不是一次性读完所有内容！

java solution

class BSTIterator {
    private Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack<>();
        pushLeftNodes(root);
    }
    
    public int next() {
        TreeNode node = stack.pop();
        //之所以判断右子树,是因为当前节点相当于根节点,其值马上要被返回,下一个最小值是当前节点的右子树根节点
        if(node.right != null) {
            pushLeftNodes(node.right);
        }
        return node.val;
    }
    
    public boolean hasNext() {
        return (!stack.isEmpty());
    }

    private void pushLeftNodes(TreeNode node) {
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}