C/C++ BM33 二叉树的镜像

文章目录

  • 前言
  • 题目
  • 解决方案一
    • 1.1 思路阐述
    • 1.2 源码
  • 总结

前言

镜像说的好听,无非就是换下节点。


题目

操作给定的二叉树,将其变换为源二叉树的镜像。
数据范围:二叉树的节点数 0 ≤ n ≤ 1000 0≤n≤1000 0n1000, 二叉树每个节点的值 0 ≤ v a l ≤ 1000 0≤val≤1000 0val1000
要求: 空间复杂度 O ( n ) O(n) O(n) 。本题也有原地操作,即空间复杂度 O ( 1 ) O(1) O(1)的解法,时间复杂度 O ( n ) O(n) O(n)

源二叉树
在这里插入图片描述

镜像二叉树
在这里插入图片描述

输入:{8,6,10,5,7,9,11}
返回值:{8,10,6,11,9,7,5}

示例2
输入:{}
返回值:{}

解决方案一

1.1 思路阐述

这个镜像其实就是交换下左右子树的节点罢了。

树的问题还是一样:拆分。

将一棵树进行镜像实际上就是对除了根节点外的所有节点与同属于同一个父节点的兄弟节点交换。

这里我们考虑根节点的为空的特殊情况进行单独返回。
后面就是把根节点下面的两个子节点进行交换,这里交换使用了一个temp的变量。

交换,这里是交换子树,不仅仅是交换值这么简单。所以第一次交换完之后,其实是左右子树都交换了。

接着对左右子树做同样的操作,直到轮到叶子结点。

通俗来讲,就是一个递归调用。大树分左树和右树。

时间复杂度分析:
对于每个节点,函数执行一些固定的操作,例如交换左右子树的指针,并对左右子树进行递归调用。因此,对于具有 n 个节点的二叉树,每个节点的操作时间是常数时间,因此时间复杂度为 O(n)。

空间复杂度分析:
递归调用会在函数调用栈上占用空间。在最坏的情况下,递归深度等于树的高度,因此空间复杂度取决于树的高度。对于平衡二叉树,空间复杂度为 O(log n),其中 n 是节点数。对于不平衡的二叉树,空间复杂度可以达到 O(n),因为递归调用可能会一直延伸到树的最深处。

综上所述,时间复杂度为 O ( n ) O(n) O(n),空间复杂度在最坏的情况下为 O ( n ) O(n) O(n),在最好的情况下为 O ( l o g n ) O(log n) O(logn)

1.2 源码

/*** struct TreeNode {*	int val;*	struct TreeNode *left;*	struct TreeNode *right;*	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pRoot TreeNode类 * @return TreeNode类*/TreeNode* Mirror(TreeNode* pRoot) {if (!pRoot)return nullptr;if(pRoot->left||pRoot->right){TreeNode *temp=pRoot->left;pRoot->left=pRoot->right;pRoot->right=temp;}pRoot->left=Mirror(pRoot->left);pRoot->right=Mirror(pRoot->right);return pRoot;}
};

总结

看了下官方的题解,还有个是栈的,感觉差不多,这里就没贴了。思路都是一样的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/320463.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

分享几个副业,一天搞100~200不成问题,一不小心收益比你主业还多

每次家庭聚会,总是那些老掉牙的话题在耳边萦绕:“孩子,你工资多少啊?买车买房了吗?”仿佛只有按部就班地上班、结婚生子,才是人生的唯一出路。 然而,在这个充满机遇的时代,谁说“不上…

【Pytorch】2.TensorBoard的运用

什么是TensorBoard 是一个可视化和理解深度爵溪模型的工具。它可以通过显示模型结构、训练过程中的指标和图形化展示训练的效果来帮助用户更好地理解和调试他们的模型 TensorBoard的使用 安装tensorboard环境 在终端使用 conda install tensorboard通过anaconda安装 导入类Sum…

华为ensp中USG6000V防火墙双机热备VRRP+HRP原理及配置

作者主页:点击! ENSP专栏:点击! 创作时间:2024年5月6日20点26分 华为防火墙双机热备是一种高可用性解决方案,可以将两台防火墙设备组成一个双机热备组,实现主备切换。当主用防火墙出现故障时&…

零基础入门学习Python第二阶01生成式(推导式),数据结构

Python语言进阶 重要知识点 生成式(推导式)的用法 prices {AAPL: 191.88,GOOG: 1186.96,IBM: 149.24,ORCL: 48.44,ACN: 166.89,FB: 208.09,SYMC: 21.29}# 用股票价格大于100元的股票构造一个新的字典prices2 {key: value for key, value in prices.i…

【强训笔记】day7

NO.1 思路:双指针模拟,begin表示最长数字字符串最后一个字符,而len表示数字字符串的长度,i用来遍历,如果为数字,那么定义j变量继续遍历,直到不为数字,i-j如果大于len,就…

优惠券样式案例

优惠券样式案例 <template><view class"box"><view class"boxItem"><img src"../../../static/come.png" alt"" class"img"/><span class"icon">&#xffe5;</span><s…

cmake进阶:文件操作

一. 简介 前面几篇文章学习了 cmake的文件操作&#xff0c;写文件&#xff0c;读文件。文章如下&#xff1a; cmake进阶&#xff1a;文件操作之写文件-CSDN博客 cmake进阶&#xff1a;文件操作之读文件-CSDN博客 本文继续学习文件操作。主要学习 文件重命名&#xff0c;删…

Flink窗口理论到实践 | 大数据技术

⭐简单说两句⭐ ✨ 正在努力的小叮当~ &#x1f496; 超级爱分享&#xff0c;分享各种有趣干货&#xff01; &#x1f469;‍&#x1f4bb; 提供&#xff1a;模拟面试 | 简历诊断 | 独家简历模板 &#x1f308; 感谢关注&#xff0c;关注了你就是我的超级粉丝啦&#xff01; &a…

vue3中标签的ref属性

组合API-ref属性 在vue2.x中&#xff0c;可以通过给元素添加refxxx属性&#xff0c;然后在代码中通过this.$refs.xxx获取到对应的元素 然而在vue3中时没有$refs这个东西的&#xff0c;因此vue3中通过ref属性获取元素就不能按照vue2的方式来获取。 目标&#xff1a;掌握使用re…

unittest_parameterized批量测试测试用例

import unittest from parameterized import parameterizeddef add(x, y):return xy"""问题&#xff1a;如果有三组数据需要测试&#xff1f;[(1,1,2), (1,2,3), (0,3,3)] """def get_data():return [(1, 2, 3), (3, 0, 3), (2, 1, 3)]# 定义测试…

win10安装DHCP服务--用于2台机器之间搭建简易网络来进入目标机器修改配置

前言&#xff1a; 客户多了&#xff0c;往往会出现各种突发情况。 比如一个客户现场没有DHCP&#xff0c;没有显示器&#xff0c;键盘。 你只有一台笔记本的情况下要配置目标机器的网络。要如何配置&#xff1f;&#xff1f; 这时候就可以使用这篇博客提供的方式了。 Windows…

低功耗UPF设计的经典案列分享

案例1 分享个例子&#xff0c;景芯A72低功耗设计&#xff0c;DBG domain的isolation为何用VDDS_maia_noncpu供电而不是TOP的VDD&#xff1f; 答&#xff1a;因为dbg的上一级是noncpu&#xff0c;noncpu下面分成dbg和两个tbnk。 案例2 景芯A72的低功耗&#xff0c;请问&#…

LangChain-RAG学习之 文档加载器

目录 一、实现原理 二、文档加载器的选择 (一).PDF 加载本地文件 可能需要的环境配置 (二).CSV 1、使用每个文档一行的 CSV 数据加载 CSVLoader 2、自定义 csv 解析和加载 &#xff08;csv_args 3、指定用于 标识文档来源的 列&#xff08;source_column (三)、文件目…

【数据可视化-02】Seaborn图形实战宝典

Seaborn介绍 Seaborn是一个基于Python的数据可视化库&#xff0c;它建立在matplotlib的基础之上&#xff0c;为统计数据的可视化提供了高级接口。Seaborn通过简洁美观的默认样式和绘图类型&#xff0c;使数据可视化变得更加简单和直观。它特别适用于那些想要创建具有吸引力且信…

(数据分析方法)长期趋势分析

目录 一、定义 二、目的 三、方法 1、移动平均法 (1)、简单移动平均法 (2)、加权移动平均法 (3)、指数平滑法 2、最小二乘法 3、线性回归 1、数据预处理 2、观察数据分布建立假设模型 3、定义损失函数 4、批量梯度下降 5、优化 4、LSTM 时序分析 5、特征工程 一…

重写muduo之EPollPoller

1、EPollPoller.h EPollPoller的主要实现&#xff1a;作为poller的派生类&#xff0c;把基类给派生类保留的这些纯虚函数的接口实现出来。 override表示在派生类里面&#xff0c;这些方法是覆盖方法。必须由编译器来保证在基类里面一定有这些函数的接口的声明。在派生类要重写…

动态库和静态库

动态库与静态库 库是写好的现有的&#xff0c;成熟的&#xff0c;可以复用的代码。现实中每个程序都要依赖很多基础的底层库&#xff0c;不可能每个人的代码都从零开始&#xff0c;因此库的存在意义非同寻常。 本质上来说库是一种可执行代码的二进制形式&#xff0c;可以被操作…

灌溉机器人 状压dp

灌溉机器人 题目描述 农田灌溉是一项十分费体力的农活&#xff0c;特别是大型的农田。小明想为农民伯伯们减轻农作负担&#xff0c;最近在研究一款高科技——灌溉机器人。它可以在远程电脑控制下&#xff0c;给农田里的作物进行灌溉。 现在有一片 N 行 M 列的农田。农田的土…

[Java EE] 多线程(八):CAS问题与JUC包

&#x1f338;个人主页:https://blog.csdn.net/2301_80050796?spm1000.2115.3001.5343 &#x1f3f5;️热门专栏:&#x1f355; Collection与数据结构 (90平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm1001.2014.3001.5482 &#x1f9c0;Java …

8个细节决定你的活动策划推广成败-华媒舍

活动策划和推广对于一个成功的活动来说至关重要。许多因素会影响活动的成功与否&#xff0c;以下我将介绍8个关键细节&#xff0c;这些细节能够决定活动的策划与推广的成败。 1. 目标定位 活动策划必须明确目标。你需要确定你的活动是为了推广何种产品或服务&#xff0c;吸引什…