Python: tiny O(1) time/O(h) space solution (amortized)


  • 4
    G
    # 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):
            self._branch = []
            self._findLeftmost(root)
        
        def _findLeftmost(self, node):
            branch = self._branch
            while node is not None:
                branch.append(node)
                node = node.left
    
        def hasNext(self):
            return bool(self._branch)
    
        def next(self):
            node = self._branch.pop()
            self._findLeftmost(node.right)
            return node.val

  • 0
    D

    self._findLeftmost() is where you store you current node, right?


Log in to reply
 

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