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!
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.
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.