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

本文主要是介绍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;
}