Leetcode173. Binary Search Tree Iterator二叉搜索树迭代器

时间:2023-03-09 07:45:56
Leetcode173. Binary Search Tree Iterator二叉搜索树迭代器

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

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

注意: next() 和hasNext() 操作的时间复杂度是O(1),并使用 O(h) 内存,其中 h 是树的高度。

二叉树的中序遍历

class BSTIterator {
public:
stack<TreeNode*> s;
TreeNode *cur;
BSTIterator(TreeNode *root) {
cur = root;
while(cur)
{
s.push(cur);
cur = cur ->left;
}
} /** @return whether we have a next smallest number */
bool hasNext() {
return !s.empty();
} /** @return the next smallest number */
int next() {
cur = s.top();
s.pop();
int res = cur ->val;
cur = cur ->right;
while(cur)
{
s.push(cur);
cur = cur ->left;
}
return res;
}
};