104ms python solution using deque and preorder traversal


  • -1
    L

    use pre-order traversal to get the sorted nodes and saved in a deque

    from collections import deque
    
    class BSTIterator(object):
        def __init__(self, root):
            """
            :type root: TreeNode
            """
            self.nodes = deque()
            self.preOrderTraversal(root, self.nodes)
    
        def preOrderTraversal(self,root, dq):
            if not root: return
            self.preOrderTraversal(root.left, dq)
            dq.appendleft(root)
            self.preOrderTraversal(root.right, dq)
    
    
        def hasNext(self):
            """
            :rtype: bool
            """
            return len(self.nodes) > 0
    
        def next(self):
            """
            :rtype: int
            """
            return self.nodes.pop().val

  • 1
    W

    but your memory is O(n) rather than O(h)


Log in to reply
 

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