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

二叉搜索树的迭代器（BSTIterator）是一种常见的数据结构，它能够按照递增顺序遍历二叉搜索树的所有节点值。通过这种方式，可以避免传统的递归方法可能带来的栈溢出问题。

核心思路

BSTIterator的实现主要基于一个堆（本文中的并非JAVA中的堆，而是基于LIFO的栈结构）来模拟递归遍历。具体来说，迭代器会在每个节点弹出堆顶元素，并将该节点的右子树节点递归地压入堆中。以下是详细的步骤：

这种方法与二叉搜索树的第二种遍历（类似于先访问左子树，后访问右子树）的顺序有关。

实现代码

#include 
   
    using namespace std;class BSTIterator {private:    stack
    
      stk;public:    BSTIterator(TreeNode* root) {        pushNode(root);    }    bool hasNext() {        return !stk.empty();    }    int next() {        TreeNode* min = stk.top();        stk.pop();        pushNode(min->right);        return min->val;    }    void pushNode(TreeNode* root) {        while (root != NULL) {            stk.push(root);            root = root->left;        }    }};
    
   

示例与测试

假设输入二叉搜索树为：

5       0   \        /    10    9          /        11

遍历结果应该是：0，0（假设根节点为5可能有多个值），5，9，10，11。

在代码运行过程中，堆的状态会在每次调用next()时有所变化：

• 初始：堆中只有根节点5。
• 第一次next()：弹出5，将其右子树（10）推入堆。
• 第二次next()：弹出10，将其右子树（9）推入堆。
• 第三次next()：弹出9，将其右子树（11）推入堆。
• 第四次next()：弹出11，堆为空，此时无法继续。

总结

BSTIterator通过使用堆来实现递归遍历，避免了传统递归方法中的栈溢出问题。这种方法在时间复杂度上与O(n)的线性扫描相当，同时空间复杂度也为O(h)，其中h是树的高度。