一、问题描述

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9

输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

二、方案一：递归法

1、思路

递归是解决树相关问题的常用方法。对于翻转二叉树，我们可以这样思考：

• 交换每个节点的左右子节点。
• 递归地对每个节点的左右子节点进行翻转。

2、代码实现

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    // 交换左右子节点
    root.Left, root.Right = root.Right, root.Left
    // 递归翻转左右子树
    invertTree(root.Left)
    invertTree(root.Right)
    return root
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。我们只需要遍历每个节点一次。
• 空间复杂度：O(n)，在最坏的情况下，树完全不平衡，递归会调用 n 次（树的高度），因此需要 O(n) 的栈空间。

三、方案二：迭代法

1、思路

迭代法通常使用队列或栈来模拟递归过程。

• 使用队列存储每一层的节点。
• 遍历队列中的每个节点，交换其左右子节点。
• 将未访问的左右子节点加入队列。

2、代码实现

func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        // 取出当前节点
        cur := queue[0]
        queue = queue[1:]
        // 交换左右子节点
        cur.Left, cur.Right = cur.Right, cur.Left
        // 将左右子节点加入队列
        if cur.Left != nil {
            queue = append(queue, cur.Left)
        }
        if cur.Right != nil {
            queue = append(queue, cur.Right)
        }
    }
    return root
}

3、复杂度分析

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。我们只需要遍历每个节点一次。
• 空间复杂度：O(n)，在最坏的情况下，树完全不平衡，队列中会包含所有节点，因此需要 O(n) 的空间。

四、总结

方案	时间复杂度	空间复杂度	备注
递归法	O(n)	O(n)	适用于所有类型的二叉树，代码简洁
迭代法	O(n)	O(n)	需要额外的队列或栈空间，适用于所有类型的二叉树

两种方法在时间复杂度上相同，但在空间复杂度上，递归法由于使用系统栈可能会受到限制，而迭代法需要显式地分配队列空间。在实际应用中，可以根据具体情况选择合适的方法。