题解 | 对称的二叉树

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        # write code here
        # 如果为空直接返回
        if not pRoot:
            return True
        node = pRoot
        ls = [node]
        k = 1 # 用于判断是否为根节点
        while ls:
            next_l = []
            if len(ls)==1 and k==1: # 根节点处理
                k=0 # 根节点只处理一次
                if node.left and node.right and node.left.val == node.right.val:
                    next_l.append(node.left)
                    next_l.append(node.right)
                elif not node.left and  not node.right: # 无子节点返回
                    return True
                else: # 左右节点的不能同时匹配
                    return False
            elif len(ls) % 2 != 0 and k==0: # 每一次的节点数必须为双数，否则不对称，返回
                return False
            else:
                for i in range(len(ls)//2):
                    node1 = ls[i]
                    node2 = ls[len(ls)-i-1]
                    if node1.left and node2.right and node1.left.val == node2.right.val:
                        pass
                    elif not node1.left and not node2.right:
                        pass
                    else:
                        return False
                    if node1.right and node2.left and node1.right.val == node2.left.val:
                        pass
                    elif not node1.right and not node2.left:
                        pass
                    else:
                        return False
                for i in range(len(ls)):
                    node = ls.pop(0)
                    if node.left:
                        next_l.append(node.left)
                    if node.right:
                        next_l.append(node.right)
            ls = next_l
        return True