当前位置: 首页 > news >正文

二叉树OJ题(C++实现)

文章目录

    • 1.二叉树的层序遍历
    • 2. 二叉树的最近公共祖先
    • 3.二叉搜索树与双向链表
    • 4.从前序与中序遍历序列构造二叉树

1.二叉树的层序遍历

二叉树的层序遍历 OJ连接

主要思路是借助一个队列,将每一层的数据以size统计,当size为0时说明该层数据已经输入完,将这一层的数据传入vector中,再通过push_back 传入 vector< vector< int >中



class Solution {
public:string tree2str(TreeNode* root) {if(root==NULL){return "";}string s;//to_string 将任意类型转换为字符串s=to_string(root->val);//只有左右子树都为空时 左子树才不加括号if(root->left==NULL&&root->right==NULL){//;}else {s+='(';s+= tree2str(root->left);s+=')';}//若右子树为空 ,则不加括号if(root->right!=NULL){s+='(';s+=  tree2str(root->right);s+=')';}return s;}
};

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

二叉树的最近公共祖先OJ连接



共分为三种情况

第一种情况

寻找节点7与0的公共祖先为 根节点3
节点7在根的左子树,而节点0在根的右子树

若一个在根的左子树,一个在根的右子树 , 则根就为公共祖先


第二种情况
以左子树为例

节点7与节点4属于根的左子树
节点7与节点4的最近公共祖先为 他们共同的父节点2


在这里插入图片描述
若两个节点都在根的左子树,则递归根的左子树的节点为根,判断两个节点是否为根的左右子树,直到寻找到


第三种情况

节点5与节点4的最近公共祖先是节点5
节点5与节点4都属于根的左子树
若两个节点都在根的左子树,则递归根的左子树的节点为根,当这个根为两个节点其中一个时,则这个节点就为公共祖先


由于第二种和第三种情况,节点都在左子树上,所以可以看作是一种情况


class Solution {
public:
bool istree(TreeNode*root,TreeNode*x)
{if(root==NULL){return false;}if(root==x){return true;}return istree(root->left,x)|| istree(root->right,x);
}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==NULL){return NULL;}//若p/q节点有一个节点为根节点,则最近公共祖先为根节点if(p==root||q==root){return root;}bool pleft=istree(root->left,p);bool pright=!pleft;bool qleft=istree(root->left,q);bool qright=!qleft;//两个节点分别在左右子树上if( (pleft&&qright)|| (pright&&qleft)){return root;}//两个节点都在根的左子树上,则递归左子树else if(pleft&&qleft){return lowestCommonAncestor(root->left,p,q);}//两个节点都在根的右子树上,则递归右子树else {return lowestCommonAncestor(root->right,p,q);}}
};

3.二叉搜索树与双向链表

二叉搜索树与双向链表OJ连接


prev节点用于记录cur节点的上一个

当cur节点值为4时,prev=NULL,因为4属于双向链表第一个节点值 所以没必要链接
只需更新prev的值为cur值即可


prev值不为空时,将cur节点与prev节点进行连接,并更新prev节点值
prev->right=cur
cur->left=prev


class Solution {public:void inconvert(TreeNode*cur,TreeNode*&prev)//因为prev是要跟着cur进行变化的,所以使用引用{if(cur==nullptr)return ;inconvert(cur->left,prev);//cur出现的顺序就为中序if(prev){prev->right=cur;cur->left=prev;}prev=cur;inconvert(cur->right,prev);}TreeNode* Convert(TreeNode* root) {TreeNode*prev=nullptr;//记录cur节点的上一个inconvert(root,prev);TreeNode*head=root;//通过遍历左子树的方式找到第一个节点while(head&&head->left){head=head->left;}return head;}
};

4.从前序与中序遍历序列构造二叉树


从前序与中序遍历序列构造二叉树OJ链接



创建root,并确定值为3
在中序数组中寻找 root值为3的节点 ,并标记其下标为rooti
再通过递归的方式分别创建root的left与root的right


同时每次都需要prev++,来确定新的根,
每次rooti都被赋值为inbegin,是为了中序数组的新区间内寻找到根


递归结束的判断条件

若rooti与inbegin都为数组中第一个数的下标时,
[inbegin, rooti-1] 即 [ 0,-1] 为不存在的区间
所以当 inbegin >inright时,就直接返回


class Solution {
public:
//prev为先序数组的下标
//inbeing与inend为 左右子树分割区间TreeNode*istree(vector<int>& preorder, vector<int>& inorder,int &prev,int inbegin,int inend){//若rooti值与inbegin同时为第一个值,//则 [inegin,rooti-1]即 [0 ,-1]会报错if(inbegin>inend){return nullptr;}//通过先序创建根节点TreeNode*root=new TreeNode();root->val=preorder[prev];//在中序数组中查找root对应的值int rooti=inbegin;while(rooti<=inend){if(preorder[prev]==inorder[rooti]){break;}rooti++;}prev++;//由于是引用,前序的根也要跟着变化//分割左右子树区间// [inbegin rooti-1] rooti [rooti+1 inend]root->left=istree(preorder,inorder,prev,inbegin,rooti-1);root->right=istree(preorder,inorder,prev,rooti+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;return  istree(preorder,inorder,i,0,inorder.size()-1);}
};

相关文章:

二叉树OJ题(C++实现)

文章目录 1.二叉树的层序遍历2. 二叉树的最近公共祖先3.二叉搜索树与双向链表4.从前序与中序遍历序列构造二叉树 1.二叉树的层序遍历 二叉树的层序遍历 OJ连接 主要思路是借助一个队列&#xff0c;将每一层的数据以size统计&#xff0c;当size为0时说明该层数据已经输入完&…...

grep -nr 命令查询字符串方式

grep -nr “搜索内容” 文件路径 其中&#xff1a; -n&#xff1a;显示行号-r&#xff1a;递归查找子目录中的文件“搜索内容”&#xff1a;要搜索的内容文件路径&#xff1a;要搜索的文件路径&#xff0c;可以是单个文件或目录路径&#xff08;将会递归搜索该目录下的所有文…...

AgentAI+ChatGPT给出答案-为什么即时通讯需要心跳

序言 人工智能ChatGpt 结合系统化的问题拆解, 现在已经能够进行问题的拆解与自问自答, 预计未来很多的脑力工作要被释放了, 作为即时通讯的开发人员, 我问问专业的问题 为什么即时通讯需要心跳 先看产品界面与使用结果 问题拆解过程 执行任务1: 概念搜索 “Executing “Res…...

跨平台跨端的登录流程及其安全设计

跨平台跨端的登录流程及其安全设计 目录 跨平台跨端的登录流程及其安全设计 一、登录流程 1.1、登录流程时序图 1.2、三方App 登录 1.3、请求的路由守卫 二、注册流程 2.1、注册流程时序图 2.2、多因素认证 2.3、自动跳转登录页面 三、涉及的技术与安全 3.1、用户…...

如何在Java中创建临时文件?

在Java程序中&#xff0c;有时需要创建临时文件来暂存数据或者执行某些操作。Java提供了许多方式来创建临时文件。在本教程中&#xff0c;我们将介绍如何使用Java标准库来创建临时文件。 一、使用File.createTempFile()方法 Java标准库中的File类提供了createTempFile()方法来…...

Vue表单基本操作-收集表单数据

收集表单数据 使用vue中的v-model收集表单里面的数据&#xff0c;不同的表单元素配合v-model会有不同的写法和技巧 本次的表单元素包括&#xff1a;文本框&#xff0c;单选&#xff0c;多选&#xff0c;下拉框&#xff0c;文本域 编写表单元素 首先编写表单元素&#xff0c;…...

Android 一个获取网址时间的Demo

Android 一个获取网址时间的Demo 文章目录 Android 一个获取网址时间的Demo通过一个网址获取时间的代码关于Android NTP 时间Android 同步时间代码 前段时间有个客户想用局域网同步Android 设备的时间&#xff0c;开发后把这个demo分享一下。 效果&#xff1a; 这里也获取了阿…...

ijkplayer解码流程源码解读

ijkplayer是一款基于ffmpeg的在移动端比较流行的开源播放器。FFmpeg是一款用于多媒体处理、音视频编解码的自由软件工程&#xff0c;采用LGPL或GPL许可证。 要想理解ijkplayer源码&#xff0c;首先得知道视频播放器的基本原理。 视频播放器播放一个互联网上的视频文件&#xf…...

2023年值得关注的3个品牌趋势,帮你弯道超车

2023年&#xff0c;大环境开放&#xff0c;压抑三年的消费蓄势待发&#xff0c;品牌如何唤醒消费者的、热情成了重中之重的大事。 春风和煦&#xff0c;万物生长。又到了各类品牌、各位营销人踌躇满志、斗志昂扬的时候了&#xff0c;浅析一下2023品牌宣传趋势&#xff0c;抓住…...

软考-高级项目管理(二十)

第20章 高级项目管理 (P572考0-2分选择 性价比很低) 在项目集管理中涉及的相关角色主要包括: 项目集发起人、项目集指导委员会、项目集经理、其他影响项目集的干系人 1.项目集发起人 项目集发起人和收益人是负责承诺将组织的资源应用于项目集&#xff0c;并致力于使项目集取得…...

RTMP协议深度解析:从原理到实践,掌握实时流媒体传输技术

目录标题 1. 引言1.1 流媒体传输技术的重要性1.2 为什么选择RTMP协议1.3 RTMP协议的发展与应用 2. RTMP协议基础2.1 RTMP协议简介2.2 RTMP协议与其他流媒体协议的比较2.3 RTMP协议的组成与工作原理 3. RTMP协议详解3.1 RTMP数据单元&#xff08;Message&#xff09;3.2 RTMP数据…...

2023mathorcup数学建模ABCD思路分析

更多思路分析&#xff0c;请看文末 A题&#xff1a;量子计算机在信用评分卡组合优化中的应用 题目提到了信用评分卡的组合优化&#xff0c;这是一个经典的优化问题。在这个问题中&#xff0c;需要通过不同的组合方式来选择不同的阈值&#xff0c;以达到最大化贷款利息收入和最…...

普通家庭,千万不要投入大量时间和金钱,让孩子去苦学和培养AI机器人编程了...

普通家庭&#xff0c;千万不要投入大量时间和金钱&#xff0c;让孩子去苦学和培养一些看似高端&#xff0c;实际却用处不大的兴趣爱好课程了&#xff0c;比如学钢琴、学音乐、学AI机器人编程这些兴趣爱好课程。 这些对孩子的成长其实意义并不大&#xff0c;尤其是AI机器人编程。…...

C++学习(day2)

文章目录 四. C中的字符串4.1 C支持两种风格的字符串4.2 string类型的赋值和初始化4.3 C风格和C风格的字符串互换4.4 string类中三个重要成员函数4.5 string类型的比较4.6 string类型的成员访问 at()6.8 string类型数据的输入 五、bool类型六、引用&#xff08;reference&#…...

软考 - IP地址与网络划分

一.IP组成 1.1 首个八位字节规则 1.2 地址掩码 IP地址掩码 标准地址掩码 A类&#xff1a;255.0.0.0 前1个字节是网络号 后3个字节是主机号 B类&#xff1a;255.255.0.0 前2个字节是网络号 后2个字节是主机号 C类&#xff1b;255.255.255.0 前3个字节是网络号 后1个字节是主机号…...

Apifox软件的基础使用方式

Apifox软件的基础使用方式 简单方便的用途 该工具是接口在线调试工具&#xff0c;这里我给到连接供大家去官网下载&#xff0c;我个人觉得是比较于postman工具好用&#xff0c;提供的语言操作是中文版本的便于操作 下载和安装 https://apifox.com/?utm_sourcebaidu&ut…...

【Tensorflow】模型如何加载HDF文件数据集?

如果每个样本都被保存为一个单独的 HDF5 文件&#xff0c;可以使用 tf.data.Dataset.list_files 函数来创建一个文件名数据集&#xff0c;然后使用 tf.data.Dataset.interleave 函数来并行读取多个文件。 下面的示例展示了如何从多个 HDF5 文件中读取数据并创建一个 tf.data.D…...

校招又临近了,怎么在面试中应对设计模式相关问题呢?

夏天开始了&#xff0c;那么夏天结束时的毕业季也不远了。毕业是个伤感、期待而又略带残酷的时节&#xff0c;就像蜜桃无论成熟与否都会在这个时间被采摘&#xff0c;如果毫无准备就踏入社会&#xff0c;就会……马上变成低级社畜。所以说还是要早点为了毕业找工作做点准备&…...

padans关于数据处理的杂谈

情况&#xff1a;业务数据基本字段会有如下&#xff1a; Index([时间, 地区, 产品, 字段, 数值], dtypeobject)这样就会引发一个经典“三角不可能定理”&#xff0c;如何同时简约展现分时序、分产品、分字段数据。&#xff09;一般来说&#xff0c; 1、时序为作为单独的分类&…...

神经网络的理解

文章目录 概念得分函数损失函数神经网络结构非线性激活函数神经网络运行过程神经网络能够做的事情概念 人工神经网络(Artificial Neural Networks,简写为ANNs)也简称为神经网络(NNs)或称作连接模型(Connection Model),它是一种模仿动物神经网络行为特征,进行分布式并…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

python报错No module named ‘tensorflow.keras‘

是由于不同版本的tensorflow下的keras所在的路径不同&#xff0c;结合所安装的tensorflow的目录结构修改from语句即可。 原语句&#xff1a; from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后&#xff1a; from tensorflow.python.keras.lay…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...