平顶山住房和城乡建设局网站,可视化编程软件,建设网站哪家便宜,做物流网站注意什么实现一个二叉搜索树迭代器类BSTIterator #xff0c;表示一个按中序遍历二叉搜索树#xff08;BST#xff09;的迭代器#xff1a;
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在…实现一个二叉搜索树迭代器类BSTIterator 表示一个按中序遍历二叉搜索树BST的迭代器
BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字且该数字小于 BST 中的任何元素。boolean hasNext() 如果向指针右侧遍历存在数字则返回 true 否则返回 false 。int next()将指针向右移动然后返回指针处的数字。
注意指针初始化为一个不存在于 BST 中的数字所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的也就是说当调用 next() 时BST 的中序遍历中至少存在一个下一个数字。 示例 输入
[BSTIterator, next, next, hasNext, next, hasNext, next, hasNext, next, hasNext]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]解释
BSTIterator bSTIterator new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next(); // 返回 3
bSTIterator.next(); // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next(); // 返回 20
bSTIterator.hasNext(); // 返回 False提示
树中节点的数目在范围 [1, 105] 内0 Node.val 106最多调用 105 次 hasNext 和 next 操作 进阶
你可以设计一个满足下述条件的解决方案吗next() 和 hasNext() 操作均摊时间复杂度为 O(1) 并使用 O(h) 内存。其中 h 是树的高度。
思路一中序遍历
c解法
class BSTIterator {
private:TreeNode* root;vectorint t;int cnt;
public:BSTIterator(TreeNode* root) : root(root), cnt(0) {stackTreeNode* s;if (root nullptr) return;while (root || !s.empty()) {while (root) {s.push(root);root root-left;}if (!s.empty()) {root s.top();s.pop();t.emplace_back(root-val);root root-right;}}}int next() {return cnt t.size() ? t[cnt] : 0;}bool hasNext() {return cnt t.size();}
};
分析
本题可转换为求二叉树的中序遍历利用栈来存储二叉树节点先放入二叉树左子树当左子树放完后再放入右子树输出的时候根据栈中节点存放位置来输出时间复杂度为O(n)空间复杂度为O(n)
总结
本题考察对二叉树中序遍历的应用利用栈来存储节点可使后面查找时的时间复杂度降低
