方法一：前序遍历

具体做法：

• “根左右”“根右左”两种方向的遍历，同步过程中如果当前两个节点同为空，则满足对称的条件，返回True。
• 当前两个节点只有一个为空或者节点值不相等，则不满足对称条件，返回False。
• 第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。

复杂度：

• 时间复杂度：O(n)，其中n为二叉树的节点数，相当于遍历整个二叉树两次；
• 空间复杂度：O(n)，最坏情况二叉树退化为链表，递归栈深度为n。

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        
        def traverse(root1, root2):
            if root1 is None and root2 is None:
                return True
            
            if root1 is None or root2 is None or root1.val != root2.val:
                return False
            return traverse(root1.left, root2.right) and traverse(root1.right, root2.left)
           
        return traverse(pRoot, pRoot)

方法二：层次遍历

从左往右遍历左子树，从右往左遍历右子树，各自遍历一半相互比对。

具体做法：

• 首先判断链表是否为空，空链表是对称的。
• 准备两个队列，分别作为从左往右层次遍历和从右往左层次遍历的辅助容器，初始第一个队列加入左节点，第二个队列加入右节点。
• 循环中每次从队列分别取出一个节点，如果都为空，暂时可以说是对称的，进入下一轮检查；如果某一个为空或是两个节点值不同，那必定不对称。其他情况暂时对称，可以依次从左往右加入子节点到第一个队列，从右往左加入子节点到第二个队列。（这里包括空节点）
• 遍历结束也没有检查到不匹配，说明就是对称的。

复杂度分析：

• 时间复杂度：O(n)，其中n为二叉树的节点个数，相当于遍历二叉树全部节点；
• 空间复杂度：O(n)，两个辅助队列的最大空间为n。

class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        if pRoot is None:
            return True
        
        s1 = []
        s2 = []

        s1.append(pRoot.left)
        s2.append(pRoot.right)

        while len(s1) and len(s2):
            left = s1.pop(0)
            right = s2.pop(0)

            if left is None and right is None:
                continue
            if left is None or right is None or left.val != right.val:
                return False
            
            s1.append(left.left)
            s1.append(left.right)

            s2.append(right.right)
            s2.append(right.left)

        return True