题目描述
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根结点初始化迭代器。
调用 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
说明
next()
和hasNext()
操作的时间复杂度是 $O(1)$,并使用 $O(h)$ 内存,其中 $h$ 是树的高度。- 你可以假设
next()
调用总是有效的,也就是说,当调用next()
时,BST 中至少存在一个下一个最小的数。
算法
(栈)
- 用栈来模拟 BST 的中序遍历过程,当前结点进栈,代表它的左子树正在被访问。栈顶结点代表当前访问到的结点。
- 求后继时,只需要弹出栈顶结点,取出它的值。然后将它的右儿子以及右儿子的左儿子等一系列结点进栈,这一步代表找右子树中的最左子结点,并记录路径上的所有结点。
- 判断是否还存在后继只需要判断栈是否为空,因为栈顶结点是下一次即将被访问到的结点。
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 {
public:
stack<TreeNode*> st;
BSTIterator(TreeNode *root) {
TreeNode *p = root;
while (p) {
st.push(p);
p = p -> left;
}
}
/** @return whether we have a next smallest number */
bool hasNext() {
return !st.empty();
}
/** @return the next smallest number */
int next() {
TreeNode *cur = st.top();
st.pop();
int v = cur -> val;
cur = cur -> right;
while (cur) {
st.push(cur);
cur = cur -> left;
}
return v;
}
};
/**
* 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();
*/
$$qpzc$$
next() 操作不是 O(1) 的吧
均摊来看,整棵树上每个结点都最多会被遍历两次
学习了
如果想把tree遍历完,然后再去调用
next()
和hasNext
,空间复杂度是O(h)吗?如果不是的话,请问是什么?把tree遍历完,就需要 $O(n)$ 的空间来存储所有点的信息。
明白了,感谢!
我也这么写的,速度击败了99%hhh