实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
示例:
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
class BSTIterator { private: vector<TreeNode*> S; public: BSTIterator(TreeNode* root){ while(root){ S.push_back(root); root = root->left; } } int next() { TreeNode* t = S.back(); S.pop_back(); int val = t->val; t = t->right; while(t){ S.push_back(t); t = t->left; } return val; } bool hasNext() { return !S.empty(); } };