大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器。”
2、题目描述
实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：
- BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
- boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
- int next()将指针向右移动，然后返回指针处的数字。 注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 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：
二、解题
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); } }
3、时间复杂度
时间复杂度：O(n)
其中n是树中节点的数量，每次调用需要O(1)的时间。
空间复杂度：O(n)
需要保存中序遍历中的全部结果。
三、总结
这道题除了可以用递归外，还可以使用栈，通过得带的方式对二叉树进行中序遍历。
然后跟递归一样，计算出中序遍历的全部结果，然后实时维护当前栈就可以了。
