LC173. 二叉搜索树迭代器

其实就相当于二叉搜索树的中序遍历，在next的时候返回一次结果。
所以可以直接存储中序遍历的所有结果在调用next方法时返回#方法一

class BSTIterator(object):
    def __init__(self, root):
        """ :type root: TreeNode """
        self.queue = collections.deque()
        self.inorder(root)
    def inorder(self,root):
        if not root:
            return 
        self.inorder(root.left)
        self.queue.append(root.val)
        self.inorder(root.right)
    def next(self):
        """ :rtype: int """
        return self.queue.popleft()


    def hasNext(self):
        """ :rtype: bool """
        return len(self.queue) > 0

也可以用迭代的方法来进行中序遍历，将迭代法进行拆分在next中返回#方法二

class BSTIterator(object):

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

    def next(self):
        """ :rtype: int """
        cur = self.stack.pop()
        node = cur.right
        while node:
            self.stack.append(node)
            node = node.left
        return cur.val

    def hasNext(self):
        """ :rtype: bool """
        return len(self.stack)>0