# INPUT
#     1
#    / \
#   2   2
#  / \ / \
# 3  4 4  3
#
# OUTPUT True
# ---
# INPUT
#     1
#    / \
#   2   2
#    \   \
#    3    3
# OUTPUT False

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

class Solution:
    def __init__(self):
        self.levels = []

    def is_list_palindrome(self, xs):
        if len(xs) < 2:
            return True
        elif xs[0] == xs[-1]:
            return self.is_list_palindrome(xs[1:-1])
        else:
            return False

    def level_order(self, root, depth):
        if len(self.levels) - 1 < depth:
            self.levels.append([])

        if root is None:
            self.levels[depth].append(None)
            return

        self.level_order(root.left, depth + 1)
        self.levels[depth].append(root.val)
        self.level_order(root.right, depth + 1)

    def are_levels_palindromes(self, levels):
        if len(levels) == 0:
            return True
        elif self.is_list_palindrome(levels[0]):
            return self.are_levels_palindromes(levels[1:])
        else:
            return False

    def isSymmetric(self, root: 'TreeNode') -> 'bool':
        if root is None:
            return True
        self.levels = []
        self.level_order(root, 0)
        return self.are_levels_palindromes(self.levels)