“实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器。”
题目链接:
来源:力扣(LeetCode)
链接: 173. 二叉搜索树迭代器 - 力扣(LeetCode)
实现一个二叉搜索树迭代器类BSTIterator ,表示一个按中序遍历二叉搜索树(BST)的迭代器:
你可以假设 next() 调用总是有效的,也就是说,当调用 next() 时,BST 的中序遍历中至少存在一个下一个数字。
示例 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:
根据二叉搜索树的性质,如果要实现二叉搜索树的迭代器,那么就需要对二叉搜索树进行中序遍历。
中序遍历就是按照左子树、根节点、右子树的方式遍历这棵树,访问左右子树的时候也按照同样的方式遍历,直到遍历整棵树。
那么这道题就是对二叉搜索树的中序遍历,将获得的结果保存到数组中。
然后,使用得到的数组来实现迭代器。
代码参考:
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);
}
}
时间复杂度:O(n)
其中n是树中节点的数量,每次调用需要O(1)的时间。
空间复杂度:O(n)
需要保存中序遍历中的全部结果。
这道题除了可以用递归外,还可以使用栈,通过得带的方式对二叉树进行中序遍历。
然后跟递归一样,计算出中序遍历的全部结果,然后实时维护当前栈就可以了。