Lc173. Binary search tree iterator

In fact, it is equivalent to the middle order traversal of binary search tree , stay next Return a result when .
So you can directly store all the results of the middle order traversal in the call next Method # Method 1

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

You can also use the iterative method to traverse the middle order , Split the iterative method into next Back in # Method 2

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