03_对称二叉树

# 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):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 当前层的节点列表
        cur_node_list = [root]

        while len(cur_node_list):
            cur_value_list = []
            next_node_list = []
            for node in cur_node_list:
                if not node:
                    cur_value_list.append(None)
                    continue
                cur_value_list.append(node.val)
                next_node_list.extend([node.left, node.right])
            if cur_value_list != cur_value_list[::-1]:
                return False
            cur_node_list = next_node_list
        return True


# leetcode 上的最优解 从两边向中间 对应的比较
class Solution2(object):
    def isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def x(p, q):
            if not p and not q:
                return True
            if not p or not q:
                return False
            if p.val == q.val:
                return x(p.left, q.right) and x(p.right, q.left)
            else:
                return False

        return x(root, root)


a = TreeNode(0)
b = TreeNode(-3)
c = TreeNode(-3)
d = TreeNode(-93)
e = TreeNode(97)
f = TreeNode(97)
g = TreeNode(-93)
h = TreeNode(-77)
i = TreeNode(-96)
j = TreeNode(-96)
k = TreeNode(-77)

a.left, a.right = b, c
b.left, b.right = d, e
c.left, c.right = f, g
d.left, d.right = h, None
e.left, e.right = i, None
f.left, f.right = j, None
g.left, g.right = None, k

root = a
s = Solution()
s.isSymmetric(a)