二叉树的镜像 - JZ18

题目描述

操作给定的二叉树，将其变换为源二叉树的镜像。

二叉树的镜像定义：

源二叉树：

        8     
       / \
      6   10
     / \ / \
    5  7 9 11

镜像二叉树：

        8
       / \
      10  6
     / \ / \
    11 9 7  5

示例：

• 输入：[8,6,10,5,7,9,11]
• 输出：[8,10,6,11,9,7,5]

说明：

• 镜像操作是将二叉树的左右子树进行交换
• 需要递归地对每个节点的左右子树进行镜像操作

解题思路

这道题有多种解法：

1. 递归法（推荐）：

   • 对于每个节点，交换其左右子树
   • 递归地对交换后的左右子树进行镜像操作

2. 迭代法（栈）：

   • 使用栈存储需要处理的节点
   • 逐个取出节点并交换其左右子树

3. 迭代法（队列）：

   • 使用队列进行层序遍历
   • 对每一层的节点交换左右子树

4. 原地操作 vs 创建新树：

   • 可以直接修改原树结构
   • 也可以创建新的镜像树

项目结构

.
├── go.mod              # Go 模块定义
├── types.go            # 二叉树类型定义和工具函数
├── solution.go         # 算法实现（你需要完成这个文件）
├── answer.go           # 参考答案（练习后查看）
├── solution_test.go    # 单元测试
└── README.md          # 说明文档

使用方法

1. 实现算法

在 solution.go 文件中实现以下函数：

• mirror(root *TreeNode) *TreeNode - 主要实现（原地镜像）

可选实现多种解法：

• mirrorRecursive(root *TreeNode) *TreeNode - 递归法
• mirrorIterativeStack(root *TreeNode) *TreeNode - 迭代法（栈）
• mirrorIterativeQueue(root *TreeNode) *TreeNode - 迭代法（队列）
• mirrorCreateNew(root *TreeNode) *TreeNode - 创建新镜像树

2. 运行测试

# 运行单元测试
go test -v

# 运行基准测试
go test -bench=.

3. 检查代码格式

# 格式化代码
go fmt ./...

# 代码检查
go vet ./...

时间和空间复杂度分析

方法	时间复杂度	空间复杂度	说明
递归法	O(n)	O(h)	h是树的高度，递归调用栈
迭代法（栈）	O(n)	O(h)	栈的最大深度为树的高度
迭代法（队列）	O(n)	O(w)	w是树的最大宽度
创建新树	O(n)	O(n)	需要创建新的树结构

其中 n 是二叉树的节点数，h 是树的高度，w 是树的最大宽度。

知识点

• 二叉树的递归操作
• 树的遍历（前序、层序）
• 栈和队列的应用
• 原地算法 vs 额外空间
• 递归与迭代的转换

注意事项

1. 空树处理： 空树的镜像仍然是空树
2. 单节点处理： 只有根节点的树，镜像后不变
3. 原地操作： 注意是否要修改原树结构
4. 递归边界： 正确处理递归的终止条件

使用迭代法（栈）

这是一个使用迭代法（栈）来实现二叉树镜像翻转的算法。让我详细解释一下：

算法目的

将二叉树进行镜像翻转，即左右子树互换位置。

核心思路

使用栈来模拟递归过程，逐层处理每个节点，交换其左右子树。

代码逐步解析

1. 边界处理

if root == nil {
    return nil
}

如果树为空，直接返回 nil。

2. 初始化栈

stack := []*TreeNode{root}

创建栈并将根节点放入，作为处理的起点。

3. 迭代处理

for len(stack) > 0 {
    // 弹出栈顶节点
    node := stack[len(stack)-1]
    stack = stack[:len(stack)-1]

当栈不为空时继续处理，每次取出栈顶节点。

4. 交换左右子树

node.Left, node.Right = node.Right, node.Left

这是核心操作：交换当前节点的左右子节点。

5. 子节点入栈

if node.Left != nil {
    stack = append(stack, node.Left)
}
if node.Right != nil {
    stack = append(stack, node.Right)
}

将存在的子节点加入栈中，等待后续处理。

执行示例

假设有这样的二叉树：

    1
   / \
  2   3
 / \
4   5

执行过程：

1. 栈：[1] → 处理节点1，交换后变成：1的左子树是3，右子树是2
2. 栈：[3, 2] → 处理节点2，交换后：2的左子树是5，右子树是4
3. 栈：[3, 5, 4] → 处理节点4（叶子节点，无变化）
4. 栈：[3, 5] → 处理节点5（叶子节点，无变化）
5. 栈：[3] → 处理节点3（叶子节点，无变化）

最终结果：

    1
   / \
  3   2
     / \
    5   4

算法特点

• 时间复杂度：O(n)，需要访问每个节点一次
• 空间复杂度：O(h)，h是树的高度，最坏情况下为O(n)
• 优点：避免了递归调用，不会有栈溢出问题
• 缺点：代码相对递归版本稍复杂

这种迭代方法特别适合处理深度很大的树，因为它不依赖系统调用栈。