[LeetCode] 173.Binary Search Tree Iterator 二叉搜索树迭代器 Implement an iterator over a binary sea
Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
这道题主要就是考二叉树的中序遍历的非递归形式,需要额外定义一个栈来辅助,二叉搜索树的建树规则就是左<根<右,用中序遍历即可从小到大取出所有节点。代码如下:
class BSTIterator {
public:
BSTIterator(TreeNode *root) {
while (root) {
s.push(root);
root = root->left;
}
}
bool hasNext() {
return !s.empty();
}
int next() {
TreeNode *n = s.top();
s.pop();
int res = n->val;
if (n->right) {
n = n->right;
while (n) {
s.push(n);
n = n->left;
}
}
return res;
}
private:
stack<TreeNode*> s;
};
--结束END--
本文标题: C++实现LeetCode(173.二叉搜索树迭代器)
本文链接: https://www.lsjlt.com/news/131705.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0