LeetCode LCR 055. 二叉搜索树迭代器

约 5 分钟
文章信息 5 个分类 7 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
树 二叉树 栈 LCR 设计 二叉搜索树 迭代器

题目描述

✅ LCR 055. 二叉搜索树迭代器

image-20260929010042968

image-20260929010042969

image-20260929010042970

题意分析

实现按中序顺序读取二叉搜索树的迭代器：next 返回下一个节点值，hasNext 判断是否仍有未返回的节点。第一次读取应得到最小值，题目保证 next 只在有后继时调用。

进阶要求操作均摊常数时间、额外空间为树高 h 的量级。可以把中序遍历的进度保存在栈中，每次只推进到下一个需要返回的节点。

解法：受控中序遍历

核心思路

[!blue]

中序遍历先访问左子树，再访问当前节点，最后访问右子树。用一个保存在迭代器对象中的栈，记录已经找到、但尚未返回的节点；方法返回后栈仍保留，下次调用就能接着遍历。

构造时从根沿左孩子一路压栈，直到空节点。最左端节点位于栈顶，也就是第一个答案；下面的节点是以后还需要返回的祖先。

每次调用 next，先弹出栈顶 cur。它左侧应返回的节点都已经处理完，因此现在轮到它。接下来中序会进入 cur 的右子树，所以再把右子树的整条左链压栈，让该子树最小的节点成为新的栈顶。

若没有右子树，不压入任何节点，栈顶就自然回到下一个尚未返回的祖先。每次操作结束时，栈顶始终是下一个最小的未返回节点，栈内其余节点只记录后续还需要访问的祖先。

每个未处理子树都会在它前面的节点返回后接入这套过程，因此栈为空就代表没有剩余节点。hasNext 只判断栈是否为空，不能弹栈或提前返回节点。

解题步骤

  1. 构造时调用压左链操作，从根开始把所有沿途节点入栈。
  2. hasNext 直接返回栈是否非空，不改变遍历进度。
  3. next 弹出栈顶节点，并从它的右孩子出发，把整条左链加入栈。
  4. 返回弹出节点的值。不断重复后，节点依次按中序被返回。

代码实现

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

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

    public int next() {
        TreeNode cur = stack.pop();

        pushLeft(cur.right);

        return cur.val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

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

type BSTIterator struct {
    stack []*TreeNode
}

func Constructor(root *TreeNode) BSTIterator {
    var stack []*TreeNode
    for ; root != nil; root = root.Left {
        stack = append(stack, root)
    }
    return BSTIterator{
        stack: stack,
    }
}

func (this *BSTIterator) Next() int {
    cur := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    for node := cur.Right; node != nil; node = node.Left {
        this.stack = append(this.stack, node)
    }
    return cur.Val
}

func (this *BSTIterator) HasNext() bool {
    return len(this.stack) > 0
}

复杂度分析

设节点数为 n，树高为 h。

  • 时间复杂度：构造为 $O(h)$，hasNext 为 $O(1)$。单次 next 最坏为 $O(h)$，因为可能压入一条左链；完整遍历中每个节点只入栈、出栈各一次，总计 $O(n)$，所以 next 均摊为 $O(1)$。
  • 空间复杂度：$O(h)$，栈中保存的是当前路径上尚未返回的部分节点，而不是全部节点值。

关键点总结

[!green]

  • 栈保存可以跨调用保留的中序遍历进度，栈顶始终是下一个答案。
  • 返回当前节点后，应转向右子树，并沿左链找到它的最小节点。
  • 单次调用可能较慢，但每个节点的入栈和出栈总次数固定，满足均摊常数时间。

易错点总结

[!yellow]

  • 构造时只压根节点：根未必是最小值，必须先压入整条左链。
  • 弹出后只压右孩子：右孩子可能还有更小的左后代，仍需压入它的整条左链。
  • 再次进入当前节点的左子树：会重复返回已经处理的节点。
  • 在 hasNext 中弹栈：查询是否还有元素也会消耗遍历进度。
  • 把均摊常数时间写成每次都为常数：某一次 next 可能遍历深度为 h 的左链。

相似题目

题目 难度 关联与区别
94. 二叉树的中序遍历 简单 同样用显式栈模拟中序，本题把一次完整遍历拆成多次next调用，保留尚未访问的路径。
285. 二叉搜索树中的中序后继 中等 本题持续产生后继序列，原题给定一个节点后直接查询一次中序后继。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/65485425
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！