方法一：递归

对称意味着整个二叉树的左右字数也是对称的。

那么将左子树的左节点与右子树的右节点比较，左子树的右节点与右子树的左节点比较，如果这样的结构下，每一个节点都相等，则该二叉树对称。中间只要有一个不相等，则一定不对称。

利用递归的方法，同步移动左右子树的指针，左子树左移时，右子树右移，反之亦然。每次检查两指针的值是否相等，全部相等则返回True，中间只要不等就返回False。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.compare(root.left, root.right)
    def compare(self, p: Optional[TreeNode], q:Optional[TreeNode]) -> bool:
        if p == None and q == None:
            return True
        if p == None or q == None:
            return False
        if p.val != q.val:
            return False
        else:
            return self.compare(p.left, q.right) and self.compare(p.right, q.left)

复杂度分析

时间复杂度：

空间复杂度：

完整测试代码

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        return self.compare(root.left, root.right)
    def compare(self, p: Optional[TreeNode], q:Optional[TreeNode]) -> bool:
        if p == None and q == None:
            return True
        if p == None or q == None:
            return False
        if p.val != q.val:
            return False
        else:
            return self.compare(p.left, q.right) and self.compare(p.right, q.left)

class main:
    a = Solution()
    node1 = TreeNode(1)
    node2 = TreeNode(2)
    node3 = TreeNode(2)
    node4 = TreeNode(3)
    node5 = TreeNode(4)
    node6 = TreeNode(4)
    node7 = TreeNode(3)

    node1.left = node2
    node1.right = node3
    node2.left = node4
    node2.right = node5
    node3.left = node6
    node3.right = node7

    b = a.isSymmetric(node1)

    print(b)

if __name__ == '__main__':
    main()

方法二：迭代

先设置一个列表，将二叉树根节点root入队两次。每次从队列中提取两个结点进行比较，为空则跳过，不同则返回False。然后将下一层的结点加入比较。加入新一层的结点时注意将两个结点的左右子节点按照相反的顺序入队。

如此重复，中间只要有不相等就返回False，循环遍历完成都相等则返回True。

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        queue = [root, root]

        while queue:
            p, q = queue.pop(), queue.pop()
            if not p and not q:
                continue
            if not p or not q:
                return False
            if p.val != q.val:
                return False

            queue.append(p.left)
            queue.append(q.right)
            queue.append(p.right)
            queue.append(q.left)
        return True

复杂度分析

时间复杂度：

空间复杂度：