标签
树
二叉树
数组
设计
日期
Oct 26, 2022
剑指 Offer II 055. 二叉搜索树迭代器
题目描述
实现一个二叉搜索树迭代器类
BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：BSTIterator(TreeNode root)初始化BSTIterator类的一个对象。BST 的根节点root会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
boolean hasNext()如果向指针右侧遍历存在数字，则返回true；否则返回false。
int next()将指针向右移动，然后返回指针处的数字。
注意，指针初始化为一个不存在于 BST 中的数字，所以对
next() 的首次调用将返回 BST 中的最小元素。可以假设
next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。示例：
题目解析
思路：
- 中序遍历将树中的节点都加入数组中，并初始化一个指针指向第一个节点，执行
next()方法的时候返回指针当前节点并且指针自增1，hasNext()方法返回指针值是否大于数组大小的布尔值