LeetCode 230.二叉搜索树中第K小的元素

各位看官们,大家好啊,今天这个题我用的方法时间复杂度比较高,但也是便于便于理解的一种方法,大家如果觉得的好的话,就给个免费的赞吧,谢谢大家了^ _ ^
题目要求如图所示:
在这里插入图片描述
题目步骤:
1.我们可以一维数组来接收各个二叉树结点的值:

	//number是数组的大小int* number = (int*)malloc(sizeof(int)*10000);//length是一维数组的长度int* length = (int*)malloc(sizeof(int));*length = 0;Preoder_trave(root,number,length);
void Preoder_trave(struct TreeNode* root,int* number,int* length)
{if(root == NULL)return;number[(*length)++] = root->val;Preoder_trave(root->left,number,length);Preoder_trave(root->right,number,length);
}

2.然后我们再用qsort排序:

qsort(number,*length,sizeof(int),intcompare);
int intcompare(const void* a,const void* b)
{return (*(int*)a - *(int*)b);
}

3.然后我们再用for循环遍历,就能找到第k个最小值了^ _ ^

    int i = 0;for(i = 0;i < *length;i++){if(i == k - 1){return number[i];}}

全部代码如下图所示:

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     struct TreeNode *left;*     struct TreeNode *right;* };*/
int intcompare(const void* a,const void* b)
{return (*(int*)a - *(int*)b);
}
void Preoder_trave(struct TreeNode* root,int* number,int* length)
{if(root == NULL)return;number[(*length)++] = root->val;Preoder_trave(root->left,number,length);Preoder_trave(root->right,number,length);
}
int kthSmallest(struct TreeNode* root, int k) {int* number = (int*)malloc(sizeof(int)*10000);int* length = (int*)malloc(sizeof(int));*length = 0;Preoder_trave(root,number,length);qsort(number,*length,sizeof(int),intcompare);int i = 0;for(i = 0;i < *length;i++){if(i == k - 1){return number[i];}}return 0;
}

好了,这就是我此题的方法,大家如果觉得好理解,就给个免费的赞吧,谢谢各位看官了^ _ ^

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

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

相关文章

值传递和址传递

值传递 上面的代码是想要交换x&#xff0c;y的值&#xff0c;把x&#xff0c;y传递给swap函数之后&#xff0c;执行下面的操作&#xff1a; 在swap中a和b交换了&#xff0c;但是和x&#xff0c;y没有关系&#xff0c;所以x&#xff0c;y在main中不会变。 址传递 下面再看把x…

技术转管理,是灾难还是奇迹?

深耕技术or转战管理&#xff1f;this is a question! 如果你还没有想好&#xff0c;那请继续往下看&#xff01; 技术专家&#xff1a;技术前瞻者、方案构建者、难题破解者、团队聚核者 管理专家&#xff1a;战略规划者、高效组织者、变革引领者、团队建设者 特点和重心都不在…

掌握特劳特定位理论核心,明晰企业战略定位之重

在当今瞬息万变的市场环境中&#xff0c;企业战略定位的重要性日益凸显。它不仅是企业在激烈竞争中保持优势的关键&#xff0c;更是企业实现长期可持续发展的基石。 哈佛大学战略学教授迈克尔波特&#xff08;Michael Porter&#xff09;指出战略就是形成一套独具的运营活动&a…

手撕设计模式——计划生育之单例模式

1.业务需求 ​ 大家好&#xff0c;我是菠菜啊。80、90后还记得计划生育这个国策吗&#xff1f;估计同龄的小伙伴们&#xff0c;小时候常常被”只生一个好“”少生、优生“等宣传标语洗脑&#xff0c;如今国家已经放开并鼓励生育了。话说回来&#xff0c;现实生活中有计划生育&…

CCAA质量管理【学习笔记】​​ 备考知识点笔记(五)质量设计方法与工具

第五节 质量设计方法与工具 1 任 务 分 解 法 1.1 概念 任务分解法&#xff0c;又称工作分解结构 (Work Breakdown Structure, 简 称 WBS) 。WBS 指以可交付成果为 导向&#xff0c;对项目团队为实现项目目标并完成规定的可交付成果而执行的工作所进行的层次分解。W…

Swift开发——循环执行方式

本文将介绍 Swift 语言的循环执行方式 01、循环执行方式 在Swift语言中,主要有两种循环执行控制方式: for-in结构和while结构。while结构又细分为当型while结构和直到型while结构,后者称为repeat-while结构。下面首先介绍for-in结构。 循环控制方式for-in结构可用于区间中的…

电子科技大学卓中卓二轮——分析笔记

1. 子系统的关键工作原理 在Linux子系统&#xff08;Subsystem for Linux, 简称WSL&#xff09;中&#xff0c;API&#xff08;应用程序编程接口&#xff09;的转换和映射是一个关键过程&#xff0c;目的是让Windows应用程序能够与Linux环境中的系统调用无缝交互。WSL使用了名…

JUnit 5学习笔记

JUnit 5 学习笔记 1.JUnit5的改变2.JUnit5常用注解及测试2.1 DisplayName/Disabled/BeforeEach/AfterEach/BeforeAll/AfterAll2.2 Timeout2.3 RepeatedTest 3.断言3.1 简单断言3.2 数组断言3.3 组合断言3.4 异常断言3.5 超时断言3.6 快速失败 4.前置条件5.嵌套测试6.参数化测试…

C++ string字符串的使用和简单模拟实现

目录 前言 1. string简介 2. string的使用和简单模拟实现 2.1 string类的定义 2.2 string(),~string()和c_str() 2.2 size&#xff0c;重载符号[ ]&#xff0c;begin和end函数 2.3 push_back&#xff0c;reserve&#xff0c;append&#xff0c;运算符重载 2.4 insert和…

12306 火车票价格解析 (PHP 解析)

1. 从接口拿数据 日期 出发站 终点站 都填上 xxx/otn/leftTicketPrice/queryAllPublicPrice?leftTicketDTO.train_date2024-06-15&leftTicketDTO.from_stationBJP&leftTicketDTO.to_stationSJP&purpose_codesADULT 返回的数据是这样的 {"validateMess…

2786. 访问数组中的位置使分数最大

这并不是一个难题,但是我确实在做题中得到了一些启发,所以记录一下 先讲一讲这个题目的做法: 首先不难想到这是一个dp问题,(由 i 可以跳到 j ) 而且应该不难, 要不然就不是medium了,doge 那么,暴力的dp就是: dp[j] max (dp[i] nums OR dp[j] dp[i] nums - x) , i<j, 前…

JVM 垃圾回收器

一、垃圾回收器类型 如果说垃圾收集算法是内存回收的方法论&#xff0c;那么垃圾收集器就是内存回收的具体 实现。下图展示了7种作用于不同分代的收集器&#xff0c;其中用于回收新生代的收集器 包括Serial、PraNew、Parallel Scavenge&#xff0c;回收老年代的收集器包括Seri…

采煤vr事故灾害应急模拟救援训练降低生命财产损失

在化工工地&#xff0c;设备繁多、环境复杂&#xff0c;潜藏着众多安全隐患&#xff0c;稍有不慎便可能引发安全事故。为了保障工地的安全&#xff0c;我们急需一套全面、高效的安全管理解决方案。web3d开发公司深圳华锐视点研发的工地安全3D模拟仿真隐患排查系统&#xff0c;正…

sql优化之利用聚簇索引减少回表次数:limit 100000,10

1. 问题描述 产品&#xff1a;我要对订单列表页做一个分页功能&#xff0c;每页10条数据&#xff0c;商家可以根据金额过滤订单 技术&#xff1a;好的&#xff0c;我写一个sql实现分页&#xff0c;x表示偏移页数&#xff0c;自测limit 10,10耗时200ms&#xff1a; SELECT * …

【2024最新精简版】MyBatis面试篇

文章目录 mybatis内部实现过程mybatis延迟加载请说说MyBatis的工作原理mybatis接口里的方法,参数不同时能重载吗mybatis分页插件的原理是什么&#xff1f;mybatis的一级、二级缓存&#x1f44d;mybatis如何实现多表查询mybatis如何实现批量插入&#x1f44d;mybatis动态SQL标签…

Spring Boot 自定义Starter

自定义starter 创建pom项目 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.ap…

可视化剪辑,账号矩阵管理,视频分发,聚合私信多功能一体化营销工具 源代码开发部署方案

可视化剪辑&#xff0c;账号矩阵管理&#xff0c;视频分发&#xff0c;聚合私信多功能一体化营销工具 源代码开发部署方案 可视化剪辑&#xff1a; 可视化剪辑开发是一种通过图形化界面和拖放操作&#xff0c;以可视化的方式进行影片剪辑和编辑的开发方法。它可以让非专业用户…

【NLP练习】Transformer中的位置编码

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 一、什么是位置编码 1. 位置编码定义 Transformer 模型中的位置编码是为了在处理序列数据时引入位置信息&#xff0c;以便模型能够分辨输入序列中不同位置的词…

180.二叉树:二叉搜索树(力扣)

代码解决 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* Tre…

实时交通 | 城市交通态势采集及可视化操作(定时运行)

一、前言 交通态势数据是关于交通状况的一种量化描述&#xff0c;它提供了关于道路网络运行状态的详细信息。交通态势数据指的是根据车流入量和车流出量的定义&#xff0c;衡量整个全局交通区域交通态势的数据。这些数据通常从车辆GPS轨迹数据中提取&#xff0c;包括车辆行驶速…