问题描述
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 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该提上日程了。