Time limit for the python solution?

• 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``````

• 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.

• 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``````

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

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

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

• 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``````

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

• ``````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
``````

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

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

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

• Has been fixed now.

• Has been fixed now.

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