gistfile1.py

# 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):
        levels = {}

        def deep_first_search(node, levels, level_so_far):
            if not node:
                val = '#'
            else:
                val = node.val

            if not level_so_far in levels:
                levels[level_so_far] = []

            levels[level_so_far].append(val)

            level_so_far += 1

            return node and (node.left or node.right) and (deep_first_search(node.left, levels, level_so_far)
                   or deep_first_search(node.right, levels, level_so_far))

        deep_first_search(root, levels, 1)

        for key in levels:
            if len(levels[key]) % 2 != 0 and key != 1:
                return False
            if levels[key] != levels[key][::-1]:
                return False

        return True