当前位置:网站首页>【LeetCode每日一题】——230.二叉搜索树中第K小的元素
【LeetCode每日一题】——230.二叉搜索树中第K小的元素
2022-07-30 00:52:00 【IronmanJay】
一【题目类别】
- 二叉树
二【题目难度】
- 中等
三【题目编号】
- 230.二叉搜索树中第K小的元素
四【题目描述】
- 给定一个二叉搜索树的根节点 root ,和一个整数 k ,请你设计一个算法查找其中第 k 个最小元素(从 1 开始计数)。
五【题目示例】
示例 1:
输入:root = [3,1,4,null,2], k = 1
输出:1
- 示例 2:
输入:root = [5,3,6,2,4,null,null,1], k = 3
输出:3
六【题目提示】
- 树中的节点数为 n 。
- 1 < = k < = n < = 1 0 4 1 <= k <= n <= 10^4 1<=k<=n<=104
- 0 < = N o d e . v a l < = 1 0 4 0 <= Node.val <= 10^4 0<=Node.val<=104
七【题目进阶】
- 如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化算法?
八【解题思路】
- 要利用二叉搜索树的特点,对二叉搜索树进行中序遍历就是从小到大的有序序列
- 所以对二叉搜索树进行中序遍历,然后存储在数组中,最后返回第k小的值就很简单了,数组是随机存取结构,可以直接返回
- 如果用C语言写的话需要注意,数组的索引不要使用index作为关键字名称,因为index是C语言的一个函数名,所以会报错重定义,使用其他关键字名称就行
九【时间频度】
- 时间复杂度: O ( n ) O(n) O(n),其中 n n n为树的结点个数
- 空间复杂度: O ( n ) O(n) O(n),其中 n n n为树的结点个数
十【代码实现】
- Java语言版
package Tree;
public class p230_TheKthSmallestElementInABinarySearchTree {
int val;
p230_TheKthSmallestElementInABinarySearchTree left;
p230_TheKthSmallestElementInABinarySearchTree right;
public p230_TheKthSmallestElementInABinarySearchTree() {
}
public p230_TheKthSmallestElementInABinarySearchTree(int val) {
this.val = val;
}
public p230_TheKthSmallestElementInABinarySearchTree(int val, p230_TheKthSmallestElementInABinarySearchTree left, p230_TheKthSmallestElementInABinarySearchTree right) {
this.val = val;
this.left = left;
this.right = right;
}
public static void main(String[] args) {
p230_TheKthSmallestElementInABinarySearchTree root = new p230_TheKthSmallestElementInABinarySearchTree(3);
p230_TheKthSmallestElementInABinarySearchTree left = new p230_TheKthSmallestElementInABinarySearchTree(1);
p230_TheKthSmallestElementInABinarySearchTree left1 = new p230_TheKthSmallestElementInABinarySearchTree(2);
p230_TheKthSmallestElementInABinarySearchTree right = new p230_TheKthSmallestElementInABinarySearchTree(4);
root.left = left;
left.right = left1;
root.right = right;
int res = kthSmallest(root, 1);
System.out.println("res = " + res);
}
private static int size;
public static int kthSmallest(p230_TheKthSmallestElementInABinarySearchTree root, int k) {
size = 0;
int[] nums = new int[10001];
inOrder(root, nums);
return nums[k - 1];
}
public static void inOrder(p230_TheKthSmallestElementInABinarySearchTree root, int[] nums) {
if (root != null) {
inOrder(root.left, nums);
nums[size++] = root.val;
inOrder(root.right, nums);
}
}
}
- C语言版
#include<stdio.h>
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int size;
void inOrder(struct TreeNode* root, int *nums)
{
if (root != NULL)
{
inOrder(root->left, nums);
nums[size++] = root->val;
inOrder(root->right, nums);
}
}
int kthSmallest(struct TreeNode* root, int k)
{
size = 0;
int nums[10001] = {
0 };
inOrder(root, nums);
return nums[k - 1];
}
/*主函数省略*/
十一【提交结果】
Java语言版
C语言版
边栏推荐
- "The lighthouse factory" of China path: smart roll out from point to surface
- How do we-media people create explosive articles?These 3 types of articles are most likely to explode
- 转发和重定向的区别及使用场景
- Since the media how to write a short video title?Three hot style title, let your video gain more traffic
- 微信开发者工具设置制表符大小为2
- Towhee 每周模型
- 推荐系统:用户“行为数据”的采集【使用Kafaka、Cassandra处理数据】【如果与业务数据重合,也需要独自采集】
- How to set up hybrid login in SQL server in AWS
- Win11的WSL2系统更换磁盘和wsl使用简介
- i.MX6U-driver development-3-new character driver
猜你喜欢
随机推荐
QTableWidget使用示例
try_catch捕获异常
exness: U.S. GDP shrinks, yen bounces back
从尾到头打印链表
SSM整合案例
Low dropout linear regulator MPQ2013A-AEC1 brand MPS domestic replacement
记笔记!电源自动测试系统测试电源纹波详细方法
【Flutter】Flutter inspector 工具使用详解,查看Flutter布局,widget树,调试界面等
Worthington解离酶:中性蛋白酶(分散酶)详情解析
npm ERR! code ENOTSUP npm ERR! notsup Unsupported engine for [email protected]: wanted: {“n
go语言解决自定义header的跨域问题
Worthington细胞分离技术丨基本原代细胞分离方法和材料
基于TNEWS‘ 今日头条中文新闻(短文本)分类
Navicat error: 1045-Access denied for user [email protected](using passwordYES)
How Navicat Connects to MySQL
Worthington解离酶:胶原酶及四个基本概况
Worthington木瓜蛋白酶&胰凝乳蛋白酶&脱氧核糖核酸酶 I
软考 --- 数据库(5)数据库控制
Toutiao We-Media Operation: How to Gain 500+ Fans in Toutiao Today?
二叉排序树(C语言)