Hi... here's my code for this problem. It doesn't look good I know... but I don't know what's wrong with it. It says "Time exceeds limit" when it is using a really big tree as the test case. Please help me... Thanks!
class Solution: # @param root, a tree node # @return a boolean def isSymmetric(self, root): if root == None: return True level1 = [root] notEmpty = True while notEmpty == True: notEmpty = False level2 = list() for node in level1: if node == None: level2.append(None) level2.append(None) else: if node.left!=None or node.right != None: notEmpty = True level2.append(node.left) level2.append(node.right) if self.isSymmetricHelper(level2)==False: return False level1 = list(level2) return True def isSymmetricHelper(self,lystOfNodes): cursor1 = 0 cursor2 = len(lystOfNodes)-1 while cursor1 < cursor2: # Both None if lystOfNodes[cursor1] == None: if lystOfNodes[cursor2] != None: return False # Both same value else: if lystOfNodes[cursor2] == None: return False elif lystOfNodes[cursor1].val != lystOfNodes[cursor2].val: return False cursor1 += 1 cursor2 -= 1
why not use recursive ?
A function judge whether its left and right are symmetric, and then the isSymmetric() call it like this:
The problem with your code is that it needs extra time to append to the list and to copy the list. For a morbidly imbalanced tree (for example, every node on the left of root only has a left child, and every node on the right of root only has a right child), the list would contain mostly Nones, so many so that the amortized running time reaches O(N^2) for such an imbalanced tree. You may want to consider a recursive solution instead, which is faster and way simpler to implement.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.