给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
思路一：递归
1、广度优先
关键点：判断左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点
一是值是否相等，二是左右子树的子节点情况是否相同
代码如下：
lass Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if root is None:
return True
def bfs(root1,root2):
if not root1 and not root2:
return True
if not root1 or not root2:
return False
if root1.val!=root2.val:
return False
return bfs(root1.left,root2.right) and bfs(root1.right,root2.left)
return bfs(root.left,root.right)
2、深度优先
深度优先搜索会不断向下，关键点在于不断的判断（增加）左子树的左节点和右节点，以及右子树的右节点和左节点
代码如下：
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
left=[]
right=[]
leftsearch(root,left)
rightsearch(root,right)
if left==right:
return True
else:
return False
def leftsearch(t,left):
if t != None:
left.append(t.val)
leftsearch(t.left,left)
leftsearch(t.right,left)
else:
left.append('null')
def rightsearch(t,right):
if t != None:
right.append(t.val)
rightsearch(t.right,right)
rightsearch(t.left,right)
else:
right.append('null')
思路二、迭代
关键点：产生一个双向队列，队列每一个元素是一对元素，比如左节点的左节点和右节点的右节点以及左节点的右节点和右节点的左节点
伪代码如下：
d=collections.dueqe()
d.append((root,root))
#不断增加队列里的元素，直至到叶子节点，队列不为空时一直判断，注意队列的每一个元素里面包含两个节点
while d:
left,right=d.popleft()
if not left and not right:
continue
if not left or not right:
return false
if left.val!=righr.val:
return false
代码如下：
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
deque=collections.deque()
deque.append([root,root])
while deque:
left,right = deque.popleft()
if not left and not right:
continue
if not left or not right:
return False
if left.val!=right.val:
return False
deque.append([left.left,right.right])
deque.append([left.right,right.left])
return True
