C++从零开始的打怪升级之路(day45)
这是关于一个普通双非本科大一学生的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代码
新手写博客,有不对的位置希望大佬们能够指出,也谢谢大家能看到这里,让我们一起学习进步吧!
相关文章:
C++从零开始的打怪升级之路(day45)
这是关于一个普通双非本科大一学生的C的学习记录贴 在此前,我学了一点点C语言还有简单的数据结构,如果有小伙伴想和我一起学习的,可以私信我交流分享学习资料 那么开启正题 今天分享的是关于二叉树的题目 1.根据二叉树创建字符串 606. 根…...
小鹅通前端实习一面
总时长35分钟,自我介绍开始 1.js和c特点上的差异; 2.js数组去重 3.js的数据类型 4.js的引用类型和值类型的差别 5.讲一下js的网络请求 6.对前端三件套和框架的理解 7.一个html文档的结构是怎样的 8.head和body的区别 9.一个页面的加载顺序(ht…...
ArrayList常用API
常见方法 add 增remove 删set 改get 查clear 清空元素size 长度isEmpty 为空判断 用法 // String就是泛型 这种使用方法对于限制类型很有用 ArrayList<String> arrayList new ArrayList<>();// add 添加元素 返回的是boolean 代表是否添加成功 arrayList.add(&qu…...
Chrome安装Axure插件
打开原型目录/resources/chrome,重命名axure-chrome-extension.crx,修改后缀为rar,axure-chrome-extension.rar 解压到axure-chrome-extension目录打开Chrome,更多工具->扩展程序,打开开发者模式,选择加…...
【AI+应用】模仿爆款视频二次创作短视频操作步骤
本来不想水这篇的, 剪辑软件估计很多人用的比我还6。 今天自己遇到1个需求,我看到一篇公众号文章的视频觉得有意思,但视频有点长,我没带耳机看视频的习惯,就想着能不能下载下来, 提取视频的音频转为文字&am…...
HTML使用
文章目录 一、简介二、HTML快速入门三、基础标签四、图片、音频、视频标签五、超链接标签六、列表标签七、表格标签八、布局标签九、表单标签十、表单向标签 一、简介 二、HTML快速入门 <html><head><title>你好</title></head><body>再…...
通过联合部署DDoS高防和WAF提升网站防护能力
如果您的网站遭受的攻击既有流量型攻击,又混杂精巧的Web应用层攻击时(例如SQL注入、跨站脚本攻击、命令注入等)时,推荐您组合使用阿里云DDoS高防和Web 应用防火墙 WAF(Web Application Firewall)࿰…...
具体挫折现象的发生以及解法思考:您如果继续不问的话,严重重责就容易来
一 积极想方设法的寻找扭转劣势的方式方法; 目前对于第一条的践行,主要还是依靠打工做事赚取收入。至于个人业务,只能往后推,往后延迟。因为不管您目前居住的环境,还是个人条件都不行,所以无法实行个人业…...
Type-C接口PD协议统一:引领电子科技新纪元的优势解析
在电子科技日新月异的今天,充电接口的统一化已经成为了业界的一大趋势。其中,Type-C接口凭借其传输速度快、使用便捷等优点,迅速成为了市场上的主流选择。而PD(Power Delivery)协议的统一,更是为Type-C接口…...
探讨2024年AI辅助研发的趋势
一、引言 随着科技的飞速发展,人工智能(AI)已经成为当今时代最具变革性的技术之一。AI的广泛应用正在重塑各行各业,其中,AI辅助研发作为科技和工业领域的一大创新热点,正引领着研发模式的深刻变革。从医药…...
Java对接海康威视摄像头实现抓图
目录 一、下载SDK 二、拷贝示例代码 三、拷贝库文件 四、运行Demo 五、抓图业务 六、调参 七、发布Linux正式环境 一、下载SDK 海康开放平台 二、拷贝示例代码 三、拷贝库文件 这时候直接运行ClientDemo会报错,因为缺失库文件! 四、运行Demo …...
浏览器一键重新发起请求
一、需求场景 在前端开发过程中,经常会需要重新请求后台进行代码调试,之前的常规方法是刷新浏览器页面或者点击页面进行交互,这样对多个请求的场景就很方便,但是往往很多时候我们只是单纯的想重新发起一个请求(多个请求…...
一起来读李清照
当然先祝各位女生节日快乐🎁🎁啦。 但是呢,今天,我们不聊技术,来聊点其他的。 大家都知道今天是三八妇女节,三八妇女节的是中国人的叫法,也叫国际妇女节。是为了纪念妇女权利的运动&#…...
找出单身狗1,2
目录 1. 单身狗12. 单身狗2 1. 单身狗1 题目如下: 思路:一部分人可能会使用对数组排序,遍历数组的方式去找出只出现一次的数字,但这种方法的时间复杂度过高,有时候可能会不满足要求。 有一种十分简便的方法是使用异或…...
贝叶斯优化BiLSTM分类预测(matlab代码)
贝叶斯优化BiLSTM分类matlab代码 数据为Excel分类数据集数据。 数据集划分为训练集、验证集、测试集,比例为8:1:1 数据处理: 在数据加载后,对数据进行了划分,包括训练集、验证集和测试集,这有助于评估模型的泛化能力。 数据标…...
Linux运维:实现光盘开机自动挂载、配置本地yum源教程
Linux运维:实现光盘开机自动挂载、配置本地yum源教程 一、光盘开机自动挂载1、检查光驱设备2、创建挂载点3、编辑/etc/fstab文件4、测试挂载 二、配置本地yum源(挂载光盘或ISO文件)1、挂载ISO文件2、创建YUM仓库配置文件3、清理YUM缓存并测试 💖The Begi…...
C语言从入门到精通 第十二章(程序的编译及链接)
写在前面: 本系列专栏主要介绍C语言的相关知识,思路以下面的参考链接教程为主,大部分笔记也出自该教程。除了参考下面的链接教程以外,笔者还参考了其它的一些C语言教材,笔者认为重要的部分大多都会用粗体标注…...
即插即用篇 | YOLOv8 引入 ParNetAttention 注意力机制 | 《NON-DEEP NETWORKS》
论文名称:《NON-DEEP NETWORKS》 论文地址:https://arxiv.org/pdf/2110.07641.pdf 代码地址:https://github.com/imankgoyal/NonDeepNetworks 文章目录 1 原理2 源代码3 添加方式4 模型 yaml 文件template-backbone.yamltemplate-small.yamltemplate-large.yaml...
基于51单片机的数字频率计设计
基于51单片机的数字频率计设计 摘要: 本文深入探讨了基于51单片机的数字频率计设计方案与实践。该设计方案不仅实现了对输入信号频率的高精度测量,还通过直观的数字显示提供了便捷的读取方式。在电子测量领域,频率作为核心参数之一,其准确测量对于确保通信、音频处理、控…...
20240307-1-前端开发校招面试问题整理JavaScript
前端开发校招面试问题整理【1】——JavaScript 1、JavaScript 基础 Q:介绍 js 的基本数据类型? 基本类型(值类型):String,Number,Boolean,Null,Undefined,S…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验
2024年初,人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目(一款融合大型语言模型能力的云端AI编程IDE)时,技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力,TRAE在WayToAGI等…...
嵌入式面试常问问题
以下内容面向嵌入式/系统方向的初学者与面试备考者,全面梳理了以下几大板块,并在每个板块末尾列出常见的面试问答思路,帮助你既能夯实基础,又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层(Link Layer) 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…...
