题解 | 对称的二叉树

（一）递归深度优先DFS，子函数可以用装饰器，也可以在类下用子函数

# 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 递归深度优先DFS，子函数可以用装饰器，也可以在类下用子函数
        def istree(l,r):
            if l==r==None:#两个都为空
                return True
            if not l or not r or l.val!=r.val:#只有一个为空或者节点值不同，不对称
                return False
            return istree(l.left,r.right) and istree(l.right,r.left)#每层对应的节点进入递归
        return istree(pRoot,pRoot)

（二）层次遍历，广度优先BFS

# 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 层次遍历，广度优先BFS
        if not pRoot:#空树为对称的
            return True
        sl, sr = [pRoot.left], [pRoot.right]#辅助队列用于从两边层次遍历
        while sl and sr:
            l, r = sl.pop(), sr.pop()#分别从左边和右边弹出节点
            if l==r==None:#都为空暂时对称
                continue
            elif not l or not r or l.val!=r.val:#某一个为空或者数字不相等则不对称
                return False
            else:
                sl += [l.left,l.right]#从左往右加入队列
                sr += [r.right,r.left]#从右往左加入队列
        return True#都检验完都是对称的