Concise python solution


  • 0
    Y
    class BSTIterator:
        # @param root, a binary search tree's root node
        def __init__(self, root):
            self.root = root
            self.path = []
    
            next_node = self.root
            while next_node:
                self.path.append(next_node)
                next_node = next_node.left
    
        # @return a boolean, whether we have a next smallest number
        def hasNext(self):
            return len(self.path) != 0
    
        # @return an integer, the next smallest number
        def next(self):
            res = self.path.pop()
            if res.right:
                succ = res.right
                while succ:
                    self.path.append(succ)
                    succ = succ.left
            return res.val

  • 0
    C

    I like this program. Better than what I wrote. But it is hard to think of this at the beginning. @youke, any experience of how you thought of this?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.