LeetCode 173. 二叉搜索树迭代器

约 5 分钟
文章信息 10 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 面试经典 150 题 字节 微软 百度 快手
标签
树 二叉树 栈 设计 二叉搜索树 迭代器

题目描述

✅ 173. 二叉搜索树迭代器

image-20260928234421500

image-20260928234421501

image-20260928234421502

题意分析

实现二叉搜索树的中序迭代器。每次调用 next() 才向前走一步并返回下一个值，第一次返回最小值；hasNext() 只判断是否还有未返回的节点，不能消耗它。

二叉搜索树的中序次序就是从小到大的次序。题目保证调用 next() 时还有下一项，并要求使用树高 $O(h)$ 的空间、均摊常数时间完成操作，所以需要保留暂停的遍历状态，而不是预先把整棵树存入数组。

解法：受控中序遍历

核心思路

[!blue]

普通中序遍历按“左子树、根、右子树”连续访问全部节点。迭代器把这个过程暂停在每次返回一个值的位置，再由下一次调用继续。显式栈保存尚未返回的祖先和当前左链，相当于保留递归中准备返回的位置。

构造时从根一路向左压栈，最后压入的节点没有更左侧节点，它就是第一次应返回的最小值。栈中更下面的祖先也尚未返回，但它们左边的遍历工作要先由上面的节点继续完成，所以不能直接按栈底顺序访问。

next() 弹出已经就绪的栈顶，它的左子树已处理完，可以返回当前值。接下来应访问它的右子树；如果右子树存在，将其根和整条左链压入栈，让右子树中最先访问的节点来到顶部。如果右子树为空，下一候选自然就是原栈中等待的祖先。

每次操作结束，栈顶仍然是最小的未返回节点。只要还有任何未访问子树，其入口路径就会保留在栈中，因此 hasNext() 直接判栈是否为空即可，不需要额外搜索或移动游标。

解题步骤

  1. 构造时调用 pushLeft(root)，把根到最左节点的路径依次压栈。
  2. next() 弹出栈顶，保存这个本次要返回的节点。
  3. 对它的右孩子调用 pushLeft，压入右子树入口到最左节点的路径，为下一次调用准备好候选。
  4. 返回刚弹出节点的值。
  5. hasNext() 仅检查栈非空，不修改栈，连续调用也不会跳过任何元素。

代码实现

class BSTIterator {
    private final Deque<TreeNode> stack = new ArrayDeque<>();

    public BSTIterator(TreeNode root) {
        pushLeft(root);
    }

    public int next() {
        // 消费已经就绪的最小节点，再展开它右子树的左链，暴露下一个候选。
        TreeNode node = stack.pop();

        pushLeft(node.right);

        return node.val;
    }

    public boolean hasNext() {
        // 仅查询状态，不弹栈或推进遍历，重复调用不影响下一项。
        return !stack.isEmpty();
    }

    // 压入待访问祖先与左链；栈顶先就绪，深层祖先的左侧工作可能尚未完成。
    private void pushLeft(TreeNode node) {
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
    }
}

type BSTIterator struct {
    stack []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
    iterator := BSTIterator{}
    iterator.pushLeft(root)
    return iterator
}

func (this *BSTIterator) Next() int {
    last := len(this.stack) - 1
    // 消费已经就绪的最小节点，再展开它右子树的左链，暴露下一个候选。
    node := this.stack[last]
    this.stack = this.stack[:last]
    this.pushLeft(node.Right)
    return node.Val
}

func (this *BSTIterator) HasNext() bool {
    // 仅查询状态，不弹栈或推进遍历，重复调用不影响下一项。
    return len(this.stack) > 0
}

// 压入待访问祖先与左链；栈顶先就绪，深层祖先的左侧工作可能尚未完成。
func (this *BSTIterator) pushLeft(node *TreeNode) {
    for node != nil {
        this.stack = append(this.stack, node)
        node = node.Left
    }
}

复杂度分析

  • 时间复杂度：构造为 $O(h)$，hasNext() 为 $O(1)$；next() 单次可能压入一条长为树高的左链，因此最坏为 $O(h)$。在完整遍历中，每个节点只压栈、弹栈各一次，总计 $O(n)$，所以每次返回的均摊成本为 $O(1)$。
  • 空间复杂度：$O(h)$，只保存当前遍历路径上待返回的节点，不保存全部访问结果；链状树的高度最坏为 n。

关键点总结

[!green]

  • 迭代器保存的是暂停的中序遍历状态，每次只消费一个节点。
  • 栈顶已经就绪，深层祖先仍需等待其左侧工作完成。
  • 弹出后展开右子树左链，维持下一项的顺序。
  • 均摊常数不代表每次最坏都是常数，完整遍历的总入栈、出栈量才是依据。

易错点总结

[!yellow]

  • 构造时只压根，不沿左链准备，第一次返回的就不一定是最小值。
  • 弹出后忽略右子树，会跳过它包含的全部节点。
  • 只压右孩子本身，未先展开它的左链，会提前返回右子树的根。
  • 在 hasNext() 中弹栈或推进遍历，重复查询会改变下一项，破坏接口语义。
  • Go 的 Next() 使用值接收者，栈切片截断等修改无法完整保留到迭代器对象中。
  • 为每次调用重新从树根搜索，会丢掉已经保存的遍历进度，无法得到当前实现的线性总成本。

相似题目

题目 难度 关联与区别
94. 二叉树的中序遍历 简单 同样用显式栈模拟中序，本题把一次完整遍历拆成多次next调用，保留尚未访问的路径。
285. 二叉搜索树中的中序后继 中等 本题持续产生后继序列，原题给定一个节点后直接查询一次中序后继。
98. 验证二叉搜索树 中等 通过中序访问利用二叉搜索树的升序性质；本题用栈保存尚未访问的后续节点，该题验证整个序列严格递增。
99. 恢复二叉搜索树 中等 通过中序访问利用二叉搜索树的升序性质；本题用栈保存尚未访问的后续节点，该题根据下降位置定位交换节点。
230. 二叉搜索树中第 K 小的元素 中等 通过中序访问利用二叉搜索树的升序性质；本题用栈保存尚未访问的后续节点，该题在第 k 次访问时取值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/29648686
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！