104ms python solution using deque and preorder traversal

  • -1

    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)
            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

    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.