173. 二叉搜索树迭代器
题目链接:173. 二叉搜索树迭代器
代码如下:
/**
* 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:
vector<TreeNode*> m_stack;//存储节点的数组
vector<TreeNode*>::iterator it;//vector迭代器
//递归中序遍历得到的是一个有序序列
void inOrder(TreeNode* root,vector<TreeNode*>& stack)
{
if(root==nullptr)
return;
inOrder(root->left,stack);
stack.push_back(root);
inOrder(root->right,stack);
}
public:
~BSTIterator(){
//我们在开始时插入了一个不存在的点,析构时手动释放掉
if(m_stack.size()>0)
{
delete m_stack[0];
m_stack.clear();
}
}
BSTIterator(TreeNode* root) {
m_stack.push_back(new TreeNode(INT32_MAX));
inOrder(root,m_stack);
it=m_stack.begin();
}
int next() {
//先自增,再取值
if(++it!=m_stack.end())
return (*it)->val;
return -1;
}
bool hasNext() {
if((it+1)==m_stack.end())
return false;
return true;
}
};
/**
* 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();
*/