Simple Python solution


  • 0
    G
    # Definition for a  binary tree node
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class BSTIterator:
        # @param root, a binary search tree's root node
        def __init__(self, root):
            self.nodes = []
            while root:
                self.nodes.append(root)
                root = root.left
    
        # @return a boolean, whether we have a next smallest number
        def hasNext(self):
            return len(self.nodes) > 0
    
        # @return an integer, the next smallest number
        def next(self):
            ret = self.nodes.pop()
            cur = ret.right
            while cur:
                self.nodes.append(cur)
                cur = cur.left
    
            return ret.val
            
    
    # Your BSTIterator will be called like this:
    # i, v = BSTIterator(root), []
    # while i.hasNext(): v.append(i.next())

  • 0
    C

    I think the time complexity of hasNext function is not O(1) in your case. I think we can add a counter to count the number of nodes in the self.nodes list, in this way the complexity of hasNext function can be reduced to O(1). Here is the code:

    # @param root, a binary search tree's root node
    def __init__(self, root):
        self.nodes = []
        self.count = 0
        while root:
            self.nodes.append(root)
            self.count += 1
            root = root.left
    
    # @return a boolean, whether we have a next smallest number
    def hasNext(self):
        return self.count > 0
    
    # @return an integer, the next smallest number
    def next(self):
        ret = self.nodes.pop()
        self.count -= 1
        cur = ret.right
        while cur:
            self.nodes.append(cur)
            self.count += 1
            cur = cur.left
        return ret.val

  • 0
    D

    Not needed. Getting the length of a list takes O(1) time


  • 0
    C

    I think you use len() function takes O(1) time, while you call len() it needs scan the list, so time is O(n).


  • 0
    D

    self.nodes is a list. Getting the length of a list takes O(1) time. List has an attribute recording its length. Please check here: https://wiki.python.org/moin/TimeComplexity


  • 0
    C

    Nice, thanks~


Log in to reply
 

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