173.Binary Search Tree Iterator

我觉得这道题吧。其实应该跟用iteration来Inorder遍历binary tree放到一起。

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        if root:
            self.stack = [root]
            while self.stack[-1].left:
                self.stack.append(self.stack[-1].left)
        else:
            self.stack = []

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


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

a = TreeNode(1)
b = TreeNode(2)
c = TreeNode(3)
b.left, b.right = a, c
v = []
s = BSTIterator(b)
while s.hasNext():
    v.append(s.next())
print v