173. Binary Search Tree Iterator

• Leetcode: https://leetcode.com/problems/binary-search-tree-iterator/

brute force 当然是直接在初始化的时候inorder 遍历完，但这样不满足 follow-up 空间复杂度O(h) 的要求，最好就是写成 iterative inorder，每次call next() 就返回一个元素值。

class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = []
        self.root = root

    def next(self) -> int:
        while self.root or self.stack:
            if self.root:
                self.stack.append(self.root)
                self.root = self.root.left
            else:
                self.root = self.stack.pop()
                res = self.root.val
                self.root = self.root.right
                return res

    def hasNext(self) -> bool:
        return True if self.root or self.stack else False