算法的学习笔记—二叉树的镜像（牛客JZ27）
😀前言
在二叉树相关的问题中，镜像操作是一个非常经典且常见的题目。本文将通过一道具体的题目，详细讲解如何将一棵二叉树转换为它的镜像，并提供实现该操作的Java代码示例。
🏠个人主页：尘觉主页
文章目录
- 😊二叉树的镜像
- 🤔问题描述
- 😉示例
- 💗数据范围
- 💗数据要求
- 🧐解题思路
- 🥳Java实现
- 🥰代码解析
- 💝空间复杂度与时间复杂度
- 😄总结
😊二叉树的镜像
牛客网
🤔问题描述
给定一棵二叉树，要求将其转换为该二叉树的镜像。换句话说，二叉树的左子树和右子树需要交换位置。
😉示例
-
示例1：
输入：
{8,6,10,5,7,9,11}输出：
{8,10,6,11,9,7,5}说明：根据输入二叉树的结构，它的镜像应该是如下形式：
比如：源二叉树
镜像二叉树
-
示例2：
输入：
{}输出：
{}说明：空树的镜像还是空树。
💗数据范围
- 二叉树的节点数
0 ≤ n ≤ 1000 - 二叉树每个节点的值
0 ≤ val ≤ 1000
💗数据要求
-
空间复杂度
O(n)。 -
本题也有原地操作，即空间复杂度
O(1)的解法，时间复杂度O(n)
🧐解题思路
将二叉树转换为镜像的操作本质上就是交换每个节点的左右子树。我们可以通过递归的方法遍历整棵树，并在每个节点上进行左右子树的交换。
具体步骤如下：
- 递归终止条件：
- 如果当前节点为
null，说明已经到达叶子节点的下一层，返回null。
- 如果当前节点为
- 交换左右子树：
- 通过一个辅助函数，将当前节点的左子树和右子树交换。
- 递归处理：
- 递归地处理左右子树，继续向下遍历，直到整个二叉树的左右子树都被交换完毕。
🥳Java实现
下面是具体的Java代码实现：
public class Solution {// 主函数，执行二叉树镜像操作public TreeNode Mirror(TreeNode root) {// 如果根节点为空，直接返回if (root == null)return root;// 交换当前节点的左右子树swap(root);// 递归处理左右子树Mirror(root.left);Mirror(root.right);// 返回镜像后的根节点return root;}// 辅助函数，交换当前节点的左右子树private void swap(TreeNode root) {// 临时存储左子树TreeNode temp = root.left;// 左子树变为右子树root.left = root.right;// 右子树变为左子树root.right = temp;}
}🥰代码解析
- Mirror方法：
- 这是主函数，用于执行二叉树的镜像操作。首先检查当前节点是否为空，如果是，直接返回
null。否则，调用swap方法交换当前节点的左右子树，然后递归处理左右子树。
- 这是主函数，用于执行二叉树的镜像操作。首先检查当前节点是否为空，如果是，直接返回
- swap方法：
- 该方法用于交换当前节点的左右子树。我们使用一个临时变量来存储左子树，然后将右子树赋值给左子树，最后将临时变量中的左子树赋值给右子树，从而完成交换。
💝空间复杂度与时间复杂度
- 空间复杂度： 在递归实现中，主要的空间消耗在于递归调用栈。最坏情况下（如二叉树为链式结构），递归深度为
O(n)，因此空间复杂度为O(n)。如果要求原地操作，理论上可以通过迭代的方式实现，空间复杂度为O(1)。 - 时间复杂度： 由于每个节点都需要访问并进行交换操作，因此时间复杂度为
O(n)。
😄总结
镜像二叉树的问题是二叉树操作中的经典问题，通过递归的方法可以高效地实现。在实际应用中，理解这个问题有助于掌握二叉树的基本操作和递归思想。这一操作在图像处理、数据结构调整等场景中都有着广泛的应用。希望通过本文的讲解，您能够掌握二叉树镜像的基本概念和实现方法。
😁热门专栏推荐
想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了，如果有什么疑问的地方请指出，诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力，今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下，创造不易您们的支持是我的动力🤞
