一、问题描述

给定一个二叉树的根节点 root，检查它是否是镜像对称的。即，交换它的左子树和右子树，两棵树是否仍然是相同的。

二、方案一：递归法

1、思路

递归比较左子树的左节点和右子树的右节点，以及左子树的右节点和右子树的左节点。如果都相等，则继续递归比较下一层。

2、代码实现

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    return checkSymmetric(root.Left, root.Right)
}
func checkSymmetric(left, 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 checkSymmetric(left.Left, right.Right) && checkSymmetric(left.Right, right.Left)
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是树中节点的数量。
• 空间复杂度：O(n)，递归调用栈的深度取决于树的高度，最坏情况下树完全不平衡，高度为 n。

三、方案二：迭代法

1、思路

使用队列进行迭代比较。首先将根节点的左右子节点放入队列中，然后每次从队列中取出两个节点比较，并将它们的子节点按对称顺序放入队列中。

2、代码实现

func isSymmetric(root *TreeNode) bool {
    if root == nil {
        return true
    }
    queue := []*TreeNode{root.Left, root.Right}
    for len(queue) > 0 {
        left, right := queue[0], queue[1]
        queue = queue[2:]
        if left == nil && right == nil {
            continue
        }
        if left == nil || right == nil {
            return false
        }
        if left.Val != right.Val {
            return false
        }
        queue = append(queue, left.Left, right.Right, left.Right, right.Left)
    }
    return true
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是树中节点的数量。
• 空间复杂度：O(n)，队列中最多存储 n/2 个节点。

四、总结

方案	时间复杂度	空间复杂度	说明
递归法	O(n)	O(n)	代码简洁，但可能会出现栈溢出
迭代法	O(n)	O(n)	需要额外的队列存储节点，但不会出现栈溢出

两种方案的时间复杂度相同，但递归法在空间复杂度上可能会更高，因为它需要使用栈空间。迭代法在空间复杂度上更优，但代码相对复杂。在实际应用中，可以根据具体情况选择使用哪种方法。