173. 二叉搜索树迭代器

class BSTIterator(object):

    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.item = []
        while root:
            self.item.append(root)
            root = root.left

    def next(self):
        """
        @return the next smallest number
        :rtype: int
        """
        cur = self.item.pop()
        cur_val = cur.val
        cur = cur.right
        while cur:
            self.item.append(cur)
            cur = cur.left
        return cur_val


    def hasNext(self):
        """
        @return whether we have a next smallest number
        :rtype: bool
        """
        return len(self.item) != 0