给定一个二叉树，检查它是否是镜像对称的。

1

/ \

2 2

/ \ / \

3 4 4 3

1

/ \

2 2

\ \

3 3

**迭代**

和[相同的树](相同的树.md)类似，遍历树节点，保存到队列中，然后依次比较

* 根节点为None，直接返回True

* 两个队列分别存储根节点的左子节点与右子节点

* 分别从两个队列中取出一个节点，进行比较

* 如果两个节点一个为None，一个不为None，则说明不对称，直接返回False

* 如果两个节点都不为None，比较节点值，如果值不相等，则说明不对称，直接返回False

* 如果值相等，按照顺序，添加节点的子节点到队列中，等待下一轮比较

class Solution:

def isSymmetric(self, root: TreeNode) -> bool:

if not root:

return True

left = root.left

right = root.right

queue1 = deque([left])

queue2 = deque([right])

while queue1 and queue2:

node1 = queue1.popleft()

node2 = queue2.popleft()

if (not node1) ^ (not node2):

# 两个子节点一个为None，一个不为None

return False

if node1 is None and node2 is None:

# 两个子节点都是None

continue

if node1.val != node2.val:

return False

left1 = node1.left

right1 = node1.right

left2 = node2.left

right2 = node2.right

queue1.append(left1)

queue2.append(right2)

queue1.append(right1)

queue2.append(left2)

return not queue1 and not queue2

**递归**

class Solution:

def check(self, p, q):

if (not p) ^ (not q):

return False

if p is None and q is None:

return True

if p.val != q.val:

return False

return self.check(p.left, q.right) and self.check(p.right, q.left)

def isSymmetric(self, root: TreeNode) -> bool:

return self.check(root, root)