173 二叉搜索树迭代器-中等

题目：

实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

• BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。

• boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。

• int next()将指针向右移动，然后返回指针处的数字。

注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。

你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

分析：

中序遍历，变成数组。

// date 2023/10/23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
type BSTIterator struct {
    index int
    values []int
}


func Constructor(root *TreeNode) BSTIterator {
    res := make([]int, 0, 16)
    stack := make([]*TreeNode, 0, 16)
    for root != nil || len(stack) != 0 {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        res = append(res, root.Val)
        root = root.Right
    }

    return BSTIterator{index: -1, values: res}
}


func (this *BSTIterator) Next() int {
    this.index++
    if this.index >= len(this.values) {
        return 0
    }
    return this.values[this.index]
}


func (this *BSTIterator) HasNext() bool {
    return this.index < len(this.values)-1
}


/**
 * Your BSTIterator object will be instantiated and called as such:
 * obj := Constructor(root);
 * param_1 := obj.Next();
 * param_2 := obj.HasNext();
 */