【力扣】101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

• 树中节点数目在范围 [1, 1000] 内
• -100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

题解：

递归法：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func isSymmetric(root *TreeNode) bool {
	var order func(left *TreeNode, right *TreeNode) bool
	order = func(left *TreeNode, right *TreeNode) bool {
		if left == nil && right == nil {
			return true
		}
		if left == nil || right == nil {
			return false
		}
		if left.Val != right.Val {
			return false
		}
		return order(left.Left, right.Right) && order(left.Right, right.Left)
	}
	return order(root.Left, root.Right)
}

迭代法（队列）：

// 时间复杂度：O(n)
// 空间复杂度：O(n)
func isSymmetric(root *TreeNode) bool {
	if root == nil {
		return true
	}
	queue := list.New()
	queue.PushBack(root)
	node := queue.Remove(queue.Front()).(*TreeNode)
	queue.PushBack(node.Left)
	queue.PushBack(node.Right)
	for queue.Len() > 0 {
		left := queue.Remove(queue.Front()).(*TreeNode)
		right := queue.Remove(queue.Front()).(*TreeNode)
		if left == nil && right == nil {
			continue
		}
		if left == nil || right == nil || left.Val != right.Val {
			return false
		}
		queue.PushBack(left.Left)
		queue.PushBack(right.Right)
		queue.PushBack(left.Right)
		queue.PushBack(right.Left)
	}
	return true
}