问题描述

二叉搜索树迭代器

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

调用 next() 将返回二叉搜索树中的下一个最小的数。

解题过程

理解题意

emm…说实话我没看懂这个题的要求，或者说不理解什么是迭代器。

所以我首先搜索了一下什么是迭代器：

百度百科：迭代器（iterator）有时又称光标（cursor），是程序设计的软件设计模式，可在容器对象（container，例如链表或数组）上遍访的接口，设计人员无需关心容器对象的内存分配的实现细节。

看了百度百科也不是很理解这题，但是看了题解，又仔细看了示例之后明白了：迭代器说白了就是用来遍历容器的工具，比如本题中需要设计的是一个遍历二叉树的迭代器，每当我们调用迭代器的next()方法时会返回当前二叉树中的最小值，而调用迭代器的hasNext()方法则是返回是否已经遍历完整棵二叉树。

（后来依稀想起来在使用STL时是眼熟过迭代器的，可以结合起来理解）

我们需要完成的就是对next()和hasNext()方法的设计和实现。

解题思路

先说说题解中的第一种思路：

首先，二叉搜索树满足：左子树上所有结点的值均小于它的根结点的值； 右子树上所有结点的值均大于它的根结点的值。

所以对二叉搜索树进行中序遍历，得到的结果就是按照从小到大排序的顺序，如果不记得了可以回顾之前做过的题：验证二叉搜索树。

因此，可以将中序遍历的结果按顺序存到一个数组当中，那么每调用一次next()则返回当前索引下的值，并将索引加1（大概就是for(int i=0;i<n;i++)的意思）；调用hasNext()就判断当前索引是不是到了最后一个，如果是的话就返回false，否则返回true。

不过在C++里我只知道能开辟一个有限范围的数组：

这样的话空间浪费太大了，所以决定用栈来存储一下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class BSTIterator {//二叉搜索树迭代器类
private:
    queue<int> q;//用来存储中序遍历的结果
public:
    BSTIterator(TreeNode* root) {//含参构造函数
        order_(root);
    }
    void order_(TreeNode* root){//中序遍历
        if(root==nullptr)
            return;
        order_(root->left);
        q.push(root->val);
        order_(root->right);
    }
    int next() {
        int result=q.front();
        q.pop();
        return result;
    }
    bool hasNext() {
        return !q.empty();
    }
};
/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

第二种思路之后再补充。

心得

学习STL该提上日程了。