判断一棵镜像二叉树

思路1.

使用层次遍历，逐层检查对称性。这是最直观的思路
对称性与结点的位置和结点的值有关，在【对称位置】上有【相同的值】才认为对称
为了体现每一层结点的位置关系，对于空结点我们使用None进行填充

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # 使用层次遍历，逐层判断是否对称
        if not root:
            return True
        
        q = list()
        q.append(root)
        while q:
            # 检查当前层是否对称
            vals = [node.val if node else None for node in q]
            if vals != vals[::-1]:
                return False
            l = len(q)
            for i in range(l):
                n = q.pop(0)
                if n:
                    q.append(n.left)
                    q.append(n.right)
        return True

思路2.

利用树自身定义的递归性，使用递归方法解决
一棵二叉树是镜像的 = root.left子树与root.right子树对称
问题转为判断两棵树是否轴对称，或者说一棵树是否是另一棵树的翻转

定义isSymmetric2(root1, root2)返回两棵树是否对称，isSymmetric(root)返回某棵树是否镜像，则

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.isSymmetric2(root.left, root.right)
        
        
    def isSymmetric2(self, root1, root2):
        # 同时为None
        if not root1 and not root2:
            return True
        # 同时不为None
        elif root1 and root2:
            return root1.val == root2.val and self.isSymmetric2(root1.left, root2.right) and self.isSymmetric2(root1.right, root2.left)
        # 任意一个为None
        else:
            return False