C++从零开始的打怪升级之路(day45)

news/2024/4/24 18:30:46/文章来源:https://blog.csdn.net/2301_80764270/article/details/136538807

这是关于一个普通双非本科大一学生的C++的学习记录贴

在此前,我学了一点点C语言还有简单的数据结构,如果有小伙伴想和我一起学习的,可以私信我交流分享学习资料

那么开启正题

今天分享的是关于二叉树的题目

1.根据二叉树创建字符串

606. 根据二叉树创建字符串

给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。

空节点使用一对空括号对 "()" 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对

仔细理解题目,可以发现这是一套基础的递归题,要注意的是括号的省略与否,左子树存在右子树不存在则可以省略,左子树不存在右子树存在则不能省略

class Solution {
public:string tree2str(TreeNode* root) {string s;if(root == nullptr)return s;s += (to_string(root->val));if(root->left){s += "(";s += tree2str(root->left);s += ")";} else if(root->right){s += "()";}if(root->right){s += "(";s += tree2str(root->right);s += ")";} return s;}
};

这是ac代码

2.二叉树的层序遍历1

102. 二叉树的层序遍历

给你二叉树的根节点 root ,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)

二叉树的层序遍历,借助queue即可,但是这里需要一层一层地输出,就需要做一些细微地调整,具体看下面的代码

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;if(root == nullptr)return vv;queue<TreeNode*> q;q.push(root);while(!q.empty()){vector<int> v;int sz = q.size();for(int i = 0; i < sz; ++i){TreeNode* front = q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}vv.push_back(v);}return vv;}
};

3.二叉树的层序遍历2

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)

这题和上面很像,但是是倒着遍历,直接操作好像没什么头绪,但是我们可以在上面题目操作完的基础上reverse以下vv,即可得到结果

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;if(root == nullptr)return vv;queue<TreeNode*> q;q.push(root);while(!q.empty()){vector<int> v;int sz = q.size();for(int i = 0; i < sz; ++i){TreeNode* front = q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}vv.push_back(v);}reverse(vv.begin(), vv.end());return vv;}
};

这是ac代码

4.二叉树的最近公共祖先

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

很明显,又是一道递归的题目,要找到最近公共祖先,我们从根开始判断,如果有一个就是根,那么直接返回根,如果不是,但是,要判断的两个结点,在树的两边子树上,那么根就是最近公共祖先,反之,向左右子树递归解决

class Solution {
public:bool Find(TreeNode* root, TreeNode* x){   if(root == nullptr)return false;if(root == x)return true;return Find(root->left, x) || Find(root->right, x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == q || root == p)return root;bool qleft, qright, pleft, pright;qleft = Find(root->left, q);    pleft = Find(root->left, p);    qright = Find(root->right, q);    pright = Find(root->right, p);if((qleft && pright) || (pleft && qright))return root;if(qleft && pleft)return lowestCommonAncestor(root->left, p, q);if(qright && pright)return lowestCommonAncestor(root->right, q, p);return nullptr;}
};

5.二叉树与双向链表

二叉搜索树与双向链表_牛客题霸_牛客网

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表

1.要求不能创建任何新的结点,只能调整树中结点指针的指向。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode,有左右指针,其实可以看成一个双向链表的数据结构

4.你不用输出双向链表,程序会根据你的返回值自动打印输出

题目给的二叉树是搜索二叉树,又叫做排序二叉树,要构造一个升序的双向链表,很显然要用到中序遍历,而中序遍历的时候,找不到他应该连的左与右,所以我们借助一个子函数来完成任务

通过cur和prev与中序遍历实现双向链表的构建,要注意的是,prev作为“贯穿”全局的角色,传参时要传引用

class Solution {
public:void _Convert(TreeNode* cur, TreeNode*& prev){if(cur == nullptr)return;_Convert(cur->left, prev);//处理cur->left = prev;if(prev)prev->right = cur;prev = cur;_Convert(cur->right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prev = nullptr;_Convert(pRootOfTree, prev);TreeNode* head = pRootOfTree;while(head && head->left)head = head->left;return head;}
};

这是ac代码

新手写博客,有不对的位置希望大佬们能够指出,也谢谢大家能看到这里,让我们一起学习进步吧!

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

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

相关文章

MySQL面试题-锁(答案版)

锁 1、MySQL 有哪些锁&#xff1f; &#xff08;1&#xff09;全局锁 加了全局锁之后&#xff0c;整个数据库就处于只读状态了&#xff0c;这时其他线程执行以下操作&#xff0c;都会被阻塞&#xff1a; 对数据的增删改操作&#xff0c;比如 insert、delete、update等语句&…

JavaScript极速入门(2)

JQuery W3C标准给我们提供了一系列函数,让我们可以操作: 网页内容 网页结构 网页样式 但是原生的JavaScript提供的API操作DOM元素时,代码比较繁琐,冗长.我们学习使用JQuery来操作页面对象. JQuery是一个快速,简洁且功能丰富的JavaScript框架,于2006年发布.它封装JavaScript常…

用开发CesiumJS模拟飞机飞行应用(一,基本功能)

本部分向您展示如何构建您的第一个 Cesium 应用程序&#xff0c;以可视化模拟从旧金山到哥本哈根的真实航班&#xff0c;并使用 FlightRadar24收集的雷达数据。您将学习如何&#xff1a; 在网络上设置并部署您的 Cesium 应用程序。 添加全球 3D 建筑物、地形和图像的基础图层。…

微服务架构 | 多级缓存

INDEX 通用设计概述2 优势3 最佳实践 通用设计概述 通用设计思路如下图 内容分发网络&#xff08;CDN&#xff09; 可以理解为一些服务器的副本&#xff0c;这些副本服务器可以广泛的部署在服务器提供服务的区域内&#xff0c;并存有服务器中的一些数据。 用户访问原始服务器…

【2024.03.05】定时执行专家 V7.1 发布 - TimingExecutor V7.1 Release

目录 ▉ 软件介绍 ▉ 新版本 V7.1 下载地址 ▉ V7.1 新功能 ▼2024-03-03 V7.1 - 更新日志 ▉ V7.0 新UI设计 ▉ 软件介绍 《定时执行专家》是一款制作精良、功能强大、毫秒精度、专业级的定时任务执行软件。软件具有 25 种【任务类型】、12 种【触发器】触发方式&#x…

【Python】成功解决TypeError: ‘float‘ object is not iterable

【Python】成功解决TypeError: ‘float’ object is not iterable &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质量合集】、PyTorch零基础入门教程&#x1f448; 希望得…

2024 GoLand激活,分享几个GoLand激活的方案

文章目录 GoLand公司简介我这边使用GoLand的理由GoLand 最新变化GoLand 2023.3 最新变化AI Assistant 正式版GoLand 中的 AI Assistant&#xff1a;_Rename_&#xff08;重命名&#xff09;GoLand 中的 AI Assistant&#xff1a;_Write documentation_&#xff08;编写文档&…

Kubernetes(k8s第四部分之servers)

1&#xff0c;为什么不使用round-robin DNS&#xff1f; 因为DNS有缓存&#xff0c;不会清理&#xff0c;无法负载均衡 ipvs代理模式&#xff0c;这种模式&#xff0c;kube-proxy会监视Kubernetes Service 对象和Endpoints&#xff0c;调用netlink接口以相应地创建ipvs规则并…

HTML使用

文章目录 一、简介二、HTML快速入门三、基础标签四、图片、音频、视频标签五、超链接标签六、列表标签七、表格标签八、布局标签九、表单标签十、表单向标签 一、简介 二、HTML快速入门 ​ <html><head><title>你好</title></head><body>再…

Linux mmap系统调用

文章目录 前言一、mmap()函数简介二、代码演示2.1 mmap使用场景2.2 私有匿名映射2.3 私有文件映射2.4 共享匿名映射2.5 共享文件映射 参考 前言 NAMEmmap, munmap - map or unmap files or devices into memorySYNOPSIS#include <sys/mman.h>void *mmap(void *addr, siz…

【金三银四的季节看下Java ORM的走向和性能对比】总结

写在最后 经过将近一周时间的框架收集、学习、实验、编码、测试市面上常见的ORM框架&#xff0c;过程中拜读了很多作者的博文、样例&#xff0c;学习很多收获很多。 重新梳理下整理的框架&#xff1a;mybatis-plus、lazy、sqltoy、mybatis-flex、easy-query、mybatis-mp、jpa、…

关于 typeof 与 instanceof 区别引出的原型对象问题

一、关于 typeof 与 instanceof 区别&#xff1a; typeof 和 instanceof 是 JavaScript 中用于检查变量类型的两个不同操作符&#xff0c;它们在使用上有着明显的区别和不同的适用场景。 typeof typeof 是一个一元操作符&#xff0c;用于返回一个变量或表达式的数据类型的字符…

常见BUG如何在测试过程中分析定位

前言 在测试的日常工作中&#xff0c;相信经常有测试的小伙伴遇到类似的情况&#xff1a;在项目上线时&#xff0c;只要出现问题&#xff08;bug&#xff09;&#xff0c;就很容易成为“背锅侠”。 软件测试人员在工作中是无法避免的要和开发人员和产品经理打交道的&#xff…

每日一题——LeetCode2575.找出字符串的可整除数组

方法一 暴力&#xff08;不可行&#xff09; 直接循序字符串&#xff0c;每次多取一位&#xff0c;转为整数型然后去除m&#xff0c;但是后面word的长度会很长&#xff0c;转为整数时会丢失精度&#xff0c;得到的结果不准确&#xff0c;如果使用大数字型BigInt()也不行&#…

开发一套小程序所需的费用取决于多个因素

随着移动互联网的发展&#xff0c;小程序已经成为许多企业和个人推广业务和服务的重要工具。 不过&#xff0c;对于很多想要开发小程序的人来说&#xff0c;最大的疑问就是开发一套小程序要花多少钱。 这个问题的答案并不是固定的&#xff0c;因为开发一个小程序的成本取决于几…

Kubernetes(K8S第三部分之资源控制器)

资源控制器 什么是控制器 Kubernetes中内建了很多controller&#xff08;控制器&#xff09;&#xff0c;这些相当于一个状态机&#xff0c;用来控制Pod的具体状态和行为。 控制器类型 ReplicationController和ReplicaSet Deployment DaemonSet StateFulSet Job/CronJob…

【ArcPy】游标访问几何数据

访问质心坐标相关数据 结果展示 代码 import arcpy shppath r"C:\Users\admin\Desktop\excelfile\a2.shp" with arcpy.da.SearchCursor(shppath, ["SHAPE","SHAPEXY","SHAPETRUECENTROID","SHAPEX","SHAPEY",&q…

前端canvas项目实战——简历制作网站(五):右侧属性栏(字体、字号、行间距)

目录 前言一、效果展示二、实现步骤1. 优化代码&#xff0c;提取常量2. 实现3个编辑模块3. 实现updateFontProperty方法4. 一个常见的用法&#xff1a;仅更新当前选中文字的样式 三、Show u the code后记 前言 上一篇博文中&#xff0c;我们扩充了线条对象&#xff08;fabric.…

MongoDB Java实战

&#x1f4d5;作者简介&#xff1a; 过去日记&#xff0c;致力于Java、GoLang,Rust等多种编程语言&#xff0c;热爱技术&#xff0c;喜欢游戏的博主。 &#x1f4d7;本文收录于MongoDB系列&#xff0c;大家有兴趣的可以看一看 &#x1f4d8;相关专栏Rust初阶教程、go语言基础…

蓝色经典免费wordpress模板主题

蓝色经典配色的免费wordpress建站主题&#xff0c;万能的wordpress建站主题。 https://www.wpniu.com/themes/24.html