☆打卡算法☆LeetCode 173. 二叉搜索树迭代器 算法解析
☆打卡算法☆LeetCode 173. 二叉搜索树迭代器 算法解析
恬静的小魔龙
发布于 2022-08-07 10:47:07
发布于 2022-08-07 10:47:07
一、题目
1、算法题目
“实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器。”
题目链接：
来源：力扣（LeetCode）
链接： 173. 二叉搜索树迭代器 - 力扣（LeetCode）
2、题目描述
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
- BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
- boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
- int next()将指针向右移动，然后返回指针处的数字。 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。
image.png
示例 1：
输入
["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示例 2：二、解题
1、思路分析
根据二叉搜索树的性质，如果要实现二叉搜索树的迭代器，那么就需要对二叉搜索树进行中序遍历。
中序遍历就是按照左子树、根节点、右子树的方式遍历这棵树，访问左右子树的时候也按照同样的方式遍历，直到遍历整棵树。
那么这道题就是对二叉搜索树的中序遍历，将获得的结果保存到数组中。
然后，使用得到的数组来实现迭代器。
2、代码实现
代码参考：
class BSTIterator {
private int idx;
private List<Integer> arr;
public BSTIterator(TreeNode root) {
idx = 0;
arr = new ArrayList<Integer>();
inorderTraversal(root, arr);
}
public int next() {
return arr.get(idx++);
}
public boolean hasNext() {
return idx < arr.size();
}
private void inorderTraversal(TreeNode root, List<Integer> arr) {
if (root == null) {
return;
}
inorderTraversal(root.left, arr);
arr.add(root.val);
inorderTraversal(root.right, arr);
}
}
image.png
3、时间复杂度
时间复杂度：O(n)
其中n是树中节点的数量，每次调用需要O(1)的时间。
空间复杂度：O(n)
需要保存中序遍历中的全部结果。
三、总结
这道题除了可以用递归外，还可以使用栈，通过得带的方式对二叉树进行中序遍历。
然后跟递归一样，计算出中序遍历的全部结果，然后实时维护当前栈就可以了。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-07-28，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录