题目：二叉搜索树迭代器

• 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
• 调用 next() 将返回二叉搜索树中的下一个最小的数。

示例：

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // 返回 3
iterator.next();    // 返回 7
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 9
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 15
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 20
iterator.hasNext(); // 返回 false

提示：

• next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用O(h)内存，其中 h 是树的高度。
• 你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。

来源：力扣（LeetCode）第173题

链接：https://leetcode-cn.com/problems/binary-search-tree-iterator

思路:

• 二叉搜索树的性质，任何一个节点的左子树都比自己小，任何一个节点的右子树都比自己大。
• 然后它还有一个性质，我在哪个地方看到的有点不记得了。就是将二叉搜索树中序遍历之后得到的值是从小到大排列的有序列表。
• 所以将二叉搜索树中序遍历就能拿到它的最小值到最大值

看代码吧:

class BSTIterator:
    def __init__(self, root: TreeNode):
        stack = []
        self.ans = []  # 储存答案
        tail = root
        while stack or tail is not None:  # 中序遍历
            if tail:
                stack.append(tail)
                tail = tail.right  # 注意和中序遍历稍有不同，因为我是用出栈的方式拿到最小值的，判断也是ans是否为空。所以我是反向的中序遍历，即中序遍历是左，中，右。而我是右，中，左。这样栈顶元素就是最小的值。
            else:
                tail = stack.pop()
                self.ans.append(tail.val)
                tail = tail.left  # 本质还是中序遍历，不用反向的应该也能做出来

    def next(self) -> int:
        return self.ans.pop()  # 最小值出栈，绝对的O(1)
        
    def hasNext(self) -> bool:
        return len(self.ans) != 0  # 这就更不用说了

复杂度分析：

• 整个程序只有中序遍历耗点时，其它两个操作根本不耗时。
• while 循环遍历整个树，
• 时间复杂度应该是 O(n) n为树的节点总和

总结：

二叉搜索树的中序遍历就是将二叉搜索树从小到大排列。