Why "time exceeds limit" with this code?


  • 0
    J

    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

  • 0
    R

    why not use recursive ?

    A function judge whether its left and right are symmetric, and then the isSymmetric() call it like this:

    IsSymmetricTree(root->left, root->right);


  • 0
    S

    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.


  • 0
    J

    Thanks! That helps!


Log in to reply
 

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