# Symmetric Tree


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    '''layer wise traverse'''
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        
        if root is None:
            return True
        
        queue = [root]
        while len(queue) != 0:
            left, right = 0, len(queue) - 1
            while left <= right:
                if queue[left] is None and queue[right] is None:
                    left += 1
                    right -= 1
                    continue
                elif queue[left] is None or queue[right] is None:
                    return False
                elif queue[left].val != queue[right].val:
                    return False
                left += 1
                right -= 1

            new_queue = []
            for node in queue:
                if node is None:
                    continue
                    
                new_queue.append(node.left)
                new_queue.append(node.right)
                
            queue = new_queue

        return True

@@ -1219,28 +1219,880 @@
 _queue%0A%0A        return True%0A
+%0A%0Aclass Solution2(object):%0A    def isSymmetric(self, root):%0A        %22%22%22%0A        :type root: TreeNode%0A        :rtype: bool%0A        %22%22%22%0A        %0A        if root == None:%0A            return True%0A%0A        stack1 = %5Broot.left%5D%0A        stack2 = %5Broot.right%5D%0A%0A        while len(stack1) != 0 and len(stack2) != 0:%0A            t1 = stack1.pop()%0A            t2 = stack2.pop()%0A            %0A            if t1 == None and t2 == None:%0A                continue%0A            elif t1 != None and t2 != None:%0A                if t1.val != t2.val:%0A                    return False%0A%0A                stack1.append(t1.left)%0A                stack2.append(t2.right)%0A%0A                stack1.append(t1.right)%0A                stack2.append(t2.left)%0A            else:%0A                return False%0A%0A        if len(stack1) != len(stack2):%0A            return False%0A        return True%0A

Update 101.py