Time Limit Exceeded


  • 0
    Z
    def isBalanced(self, root):
        if not root: 
            return True 
        else: 
            return abs(self.maxDepth(root.left) - self.maxDepth(root.right)) <= 1 and self.isBalanced(root.left) and self.isBalanced(root.right)
    
    def maxDepth(self, root):
        if not root: 
            return 0 
        else: 
            return max(self.maxDepth(root.left), self.maxDepth(root.left)) + 1 
    

    OJ says "Time Limit Exceeded". Someone please help! Thanks a lot!


  • 1

    Your line

    return max(self.maxDepth(root.left), self.maxDepth(root.left)) + 1
    

    is wrong, the second root.left should be root.right.

    After fixing that, it's fast enough to get accepted. It's in the second "hill" of the runtime distribution, though. That distribution looks quite interesting. I suspect the slower hill is solutions like yours which recompute depths, and the faster hill is solutions which don't.


  • 0
    Z

    Thanks Stefan! I looked through the other approach: instead of getting the height of each node, we can get the height of that node. This way is much faster indeed.


  • 0

    Not sure what you mean... What's the difference between "getting the height of each node" and "get the height of that node"?


Log in to reply
 

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