clean Python solution using stack beats 100%


  • 1
    J

    It's actually in-order traversal.

    
    # Definition for a  binary tree node
    # 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
            """
            self.stack = []
            while root:
                self.stack.append(root)
                root = root.left
        
        def hasNext(self):
            """
            :rtype: bool
            """
            if self.stack:
                return True
            else:
                return False
                
        def next(self):
            """
            :rtype: int
            """
            ele = self.stack.pop()
            right = ele.right
            while right:
                self.stack.append(right)
                right = right.left
            return ele.val
    
    # Your BSTIterator will be called like this:
    # i, v = BSTIterator(root), []
    # while i.hasNext(): v.append(i.next())
    

Log in to reply
 

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