本文共 1807 字，大约阅读时间需要 6 分钟。

BSTIterator是一种用于按中序遍历二叉搜索树（BST）的迭代器。该迭代器通过维护一个指针，逐步访问树中的节点，返回中序遍历的结果。以下是BSTIterator的实现思路和代码示例。

实现思路

这种方法确保了每次next()和hasNext()操作的时间复杂度为O(1)，并且只需额外存储与树的高度成正比的空间。

代码示例

import java.util.ArrayList;
import java.util.List;
class BSTIterator {
    private List
   
     list;
    private int count = 0;
    private int size = 0;
    public BSTIterator(TreeNode root) {
        if (root == null) {
            size = 0;
            return;
        }
        List
    
      list = new ArrayList<>();
        this.list = list;
        this.size = 0;
        this.digui(root, list);
        this.size = list.size();
    }
    private void digui(TreeNode node, List
     
       list) {
        if (node == null) {
            return;
        }
        if (node.left != null) {
            digui(node.left, list);
        } else {
            list.add(node.val);
        }
        if (node.right != null) {
            digui(node.right, list);
        } else {
            list.add(node.val);
        }
        size = list.size();
    }
    public int next() {
        if (count <= size - 1) {
            return list.get(count++);
        } else {
            return null;
        }
    }
    public boolean hasNext() {
        return count <= size - 1;
    }
}
     
    
   

代码解释

这种方法确保了迭代器能够按中序顺序访问BST中的节点，并且每次操作的时间复杂度为O(1)，空间复杂度为O(h)，其中h是树的高度。