Time limit for the python solution?


  • 7
    S

    Hi my algorithm is o((log n)^2) and it still can't pass the special judge, any idea why?
    my code is as follows:
    it checks the leftmost and rightmost nodes and if they are on the same level, then the nodes in this full complete tree is added, otherwise break the two subtrees and calculate the number of nodes in each separately.

    class Solution:
        # @param {TreeNode} root
        # @return {integer}
        def countNodes(self, root):
            if not root:
                return 0
            h1=h2=0
            node=root
            while node:
                h1+=1
                node=node.left
            node=root
            while node:
                h2+=1
                node=node.right
            if h1==h2:
                return 2**h1-1
            return self.countNodes(root.left)+self.countNodes(root.right)+1

  • 0

    I wrote several different Python O((log n)^2) solutions and can't get any accepted, either. I think there's something wrong with the judge.


  • 0
    S

    Here is mine, still TLE

    def countNodes(self, root):
        ret = 0
        hleft = 0
        p = root
        while p:
            p = p.left
            hleft += 1
            
        while root:
            hright = 1
            p = root.right
            while p:
                p = p.left
                hright += 1
            if hleft == hright:
                root = root.right
                ret += 1 << (hleft - 1)
                hleft = hright - 1
            else:
                root = root.left
                ret += 1 << (hright - 1)
                hleft = hleft - 1
        return ret

  • 0
    S

    I ported same code as above to cpp, 80ms passed. So looks like there is some issue in the OJ system.


  • 0

    I have just fixed this issue. Please try submitting again, your solution should pass the judge now. :)


  • 0

    I have just fixed this issue. Please try submitting again, your solution should pass the judge now. :)


  • 0

    No, still doesn't work, still "Time Limit Exceeded" for "Special Judge: very large tree". And I actually get that even for this:

    class Solution:
        def countNodes(self, root):
            return 1

  • 0
    Z

    hi , I also meet the same problem .the solution of alg is also o((log n)^2)


  • 0
    W
    class Solution:
        # @param {TreeNode} root
        # @return {integer}
        def countNodes(self, root):
            height = self.calculateHeight(root)
            if height == 0: return 0
            if height == 1: return 1
            bt = 0
            ed = 1 << (height - 1) - 1
            while bt <= ed:
                mid = bt + (ed - bt) / 2
                if self.isNodeExist:
                    bt = mid + 1
                else:
                    ed = mid - 1
            
            return 2 ** (height - 1) - 1 + bt
    
    
        def calculateHeight(self, root):
            height = 0
            while root is not None:
                height += 1
                root = root.left
            return height
    
        def isNodeExist(self, mid, height, root):
            high = 0
            stand = 1 << (height - 2)
    
            while high < height - 1 and root != None:
                if mid & stand == 1:
                    root = root.right
                else:
                    root = root.left
                mid <<= 1
                high += 1
    
            if root != None:
                return True
            else:
                return False
    

  • 0
    Z

    Could you please help to check is there any accepted python solution now?


  • 0
    C

    @1337c0d3r getting TLE even just returning 1....


  • 0
    C

    the error is still there, getting TLE even just returning 1...


  • 0

    The judge has been changed and good Python solutions should now get accepted in 300-400 ms.


  • 0

    Has been fixed now.


  • 0

    Has been fixed now.


Log in to reply
 

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