Binary Tree Iterator

题目描述

解题方法

将in-order的过程分拆就可以了

Solution

class BSTIterator(object):
    def __init__(self, root):
        """
        :type root: TreeNode
        """
        self.stack = []
        self.pushLeftChildren(root)

    def pushLeftChildren(self, root):
        while root:
            self.stack.append(root)
            root = root.left

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

    def next(self):
        """
        :rtype: int
        """
        if self.stack:
            top = self.stack.pop()
            self.pushLeftChildren(top.right)
            return top.val

Reference