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

Categories:

题目描述
思路分析
1. 解法一：栈模拟中序遍历（推荐）
相似题目

题目描述

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

思路分析

解法一：栈模拟中序遍历（推荐）

核心思路：

中序遍历 BST 得到递增序列。

用栈保存当前节点到最左路径。

next 弹出栈顶并处理其右子树的最左路径。

复杂度分析：

时间复杂度：均摊 O(1)，每个节点仅进栈出栈一次。

空间复杂度：O(h)，其中 h 表示树高。

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

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

    public int next() {
        TreeNode node = stack.pop();
        if (node.right != null) {
            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 {
    it := BSTIterator{stack: make([]*TreeNode, 0)}
    it.pushLeft(root)
    return it
}

func (it *BSTIterator) Next() int {
    node := it.stack[len(it.stack)-1]
    it.stack = it.stack[:len(it.stack)-1]

    if node.Right != nil {
        it.pushLeft(node.Right)
    }

    return node.Val
}

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

func (it *BSTIterator) pushLeft(node *TreeNode) {
    for node != nil {
        it.stack = append(it.stack, node)
        node = node.Left
    }
}

相似题目

题目	难度	考察点
94. 二叉树的中序遍历	中等	栈、遍历
230. 二叉搜索树中第K小的元素	中等	BST
653. 两数之和 IV - 输入 BST	简单	BST
173. 二叉搜索树迭代器	中等	栈
98. 验证二叉搜索树	中等	BST

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/65485425