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;
}
好了，这就是我此题的方法，大家如果觉得好理解，就给个免费的赞吧，谢谢各位看官了^ _ ^