题解 | #对称的二叉树#

法一：递归（搬运牛客题解官）

step 1：两种方向的前序遍历，当前同步走的两个节点同为空，属于对称的范畴。（递归终止条件）

step 2：当前两个节点只有一个为空或者节点值不相等，不是对称的二叉树。（递归终止条件）

step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param pRoot TreeNode类 
# @return bool布尔型
#
class Solution:
    def recursion(self,root1,root2):
        #递归终止条件
        if root1 ==None and root2 ==None:
            return True
        elif root1 ==None or root2 ==None or root1.val!=root2.val:
            return False
        #递归
        return self.recursion(root1.left,root2.right) and self.recursion(root1.right,root2.left)
        
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        return self.recursion(pRoot,pRoot)#之所以需要设计这样的return，是因为规定的isSymmetrical的输入不好直接设置递归。

法二：借助队列层次遍历。 从左往右遍历根的左子树，从右往左遍历根右子树，各自遍历一半相互比对。