[LeetCode 101] Symmetric Tree

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

class Solution:
    # @param root, a tree node
    # @return a boolean
    def isSymmetric(self, root):
        """
        We traverse the tree from the root level by level.
        For each level, we construct a integer array of length 2^depth,
        then we check if the array is symmetric.
        """
        if not root:
            return True
        q = [root]
        next = True
        while next:
            next = False
            new_q = []
            numbers = []
            for node in q:
                if node:
                    numbers.append(node.val)
                    # Left child
                    if node.left:
                        next = True
                        new_q.append(node.left)
                    else:
                        new_q.append(None)
                    # Right child
                    if node.right:
                        next = True
                        new_q.append(node.right)
                    else:
                        new_q.append(None)
                else:
                    numbers.append(0)
            if not self.isSymmetricList(numbers):
                return False
            q = new_q
        return True

    def isSymmetricList(self, lst):
        low = 0
        high = len(lst)-1
        while low < high:
            if lst[low] != lst[high]:
                return False
            low += 1
            high -= 1
        return True