我要评论各位看官们，大家好啊，今天这个题我用的方法时间复杂度比较高，但也是便于便于理解的一种方法，大家如果觉得的好的话，就给个免费的赞吧,谢谢大家了^ _ ^
题目要求如图所示:
题目步骤：
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;
}
好了，这就是我此题的方法，大家如果觉得好理解，就给个免费的赞吧，谢谢各位看官了^ _ ^
发表评论