题目描述
实现一个二叉搜索树迭代器，使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
示例
迭代器有两个方法：next() 和 hasNext()
来源：https://leetcode-cn.com/problems/binary-search-tree-iterator/
背景
二叉搜索树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。
简单来说就是所有节点都遵循：左节点<根节点<右节点
已知条件
TreeNode，其中只有左节点left和又节点right
思路
由于二叉搜索树的特性，最小的节点一定是最“左”的节点，第二小的节点一定是最左节点的根节点，所以按照中序遍历的方式即可得到从小到大的序列。
工具：栈
方法：从根节点开始，将根节点及其所有左节点依次入栈，每次调用next时，从栈顶出一个节点，此节点即为当前最小的节点，暂且称为节点A
考虑问题：
- 如果A是叶子节点，那个下一个最小节点一定是A的父节点，此时直接将A出栈即可
2.由于前边把所有左节点都入栈了，所以L节点不可能有左节点，但是可能有右节点，如果有右节点，不妨称为R，那么当前栈顶节点（不妨称为P）一定比R大，因为L是P的左节点，所以P>L及L的所有子节点，所以下一个最小的节点一定在R及R的子节点中，现在问题变为找到R及R子节点中最小的节点，这个问题就是当前在解决的问题，只不过规模小一点而已，所以还是按照前面做的：把R及R的左节点依次入栈，此时栈顶的节点一定又是最小的节点
实现
class BSTIterator(var root: TreeNode?) {
val stack = LinkedList<TreeNode>()
init {
root?.let {
pushData(it)
}
}
fun pushData(treeNode: TreeNode?) {
treeNode?.let {
stack.push(it) //将父节点入栈
var node: TreeNode = it
while (node.left != null) {//循环遍历父节点的所有左节点，依次入栈
stack.push(node.left)
node = node.left!!
}
}
}
//迭代器方法
fun next(): Int {
var node = stack.pop() //栈顶节点一定是最小的节点
pushData(node.right)//如果当前栈顶节点的右节点不为空，那么需要把右节点中的所有左节点再次入栈，保证栈顶节点一定是最小的节点
return node.value
}
//迭代器方法
fun hasNext(): Boolean {
return !stack.isEmpty() //栈为空则遍历完了
}
class TreeNode(var value: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
}
