题目
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题方法
两颗树互为镜像，则两颗树拥有相同的根节点，
每颗数的右子树都与另一颗树的左子树进行对称。
递归
设置两个指针进行同步移动
如果两个指针指向节点都为空，说明两个指针都遍历完了树，说明两棵树是对称二叉树
如果指针其中一颗树的指针为空，但另一颗还不为空，说明两棵树不对称
判断当前两颗数指向节点值是否相同，如果不相同，说明两棵树不对称
继续递归，拿左子树的左节点与右子树的右节点比较，拿左子树的右节点和右子树的左节点比较
时间复杂度:O(n)
空间复杂度:O(n) 空间复杂度与递归使用的栈空间有关，递归层数不超过n个节点
迭代
与递归思路基本一致
初始化时把两个根节点放入队列
开始迭代，直到队列元素为空结束
然后两两从队列中取出，判断两节点是否符合镜像节点要求
符合要求则继续把左右子树需要比较的镜像节点两两放入队列
时间复杂度:O(n)
空间复杂度:O(n) 队列空间大小，每个元素最多进队列一次，出队列一次，队列中最多不超过n个节点元素
代码
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// 递归
func isSymmetric(root *TreeNode) bool {
// 从根节点出发，也可以忽略根节点
return check(root, root)
}
func check(l, r *TreeNode) bool {
// 两子树同时遍历完了说明对称
if l == nil && r == nil {
return true
}
// 其中一个子树先遍历完说明不对称
if l == nil || r == nil {
return false
}
// 判断当前两对称节点是否相等，递归判断剩余对称节点是否符合要求
return l.Val == r.Val && check(l.Left, r.Right) && check(l.Right, r.Left)
}
// 迭代
func isSymmetric2(root *TreeNode) bool {
// 初始化队列元素(根节点)，同样也可以忽略根节点
// var l,r *TreeNode
// var queue []*TreeNode
// queue = append(queue,root.Left)
// queue = append(queue,root.Right)
l,r := root,root
var queue []*TreeNode
queue = append(queue,l)
queue = append(queue,r)
for len(queue) > 0{
// 两两从队列取出元素
l,r = queue[0],queue[1]
queue = queue[2:]
// 判断是否符合对称规则
if l == nil && r == nil{
continue
}
if l == nil || r == nil{
return false
}
if l.Val != r.Val{
return false
}
// 将下一轮要比较的对称节点放入队列
queue = append(queue,l.Left)
queue = append(queue,r.Right)
queue = append(queue,l.Right)
queue = append(queue,r.Left)
}
return true
}