分類標(biāo)簽：鏈表? ? ? ? ? ? ? ?
難易度：中等
題目描述：
將一個按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。本題中，一個高度平衡二叉樹是指一個二叉樹每個節(jié)點(diǎn)?的左右兩個子樹的高度差的絕對值不超過 1。
示例:
給定有序數(shù)組: [-10,-3,0,5,9],
一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹：
? ? ? 0
? ? / \
? -3? 9
? /? /
-10? 5
思路：轉(zhuǎn)換成數(shù)組+二分法+遞歸
1.利用空間使用更多的空間來降低時間的復(fù)雜度；
2.在遞歸過程中對鏈表的制作處理會比較繁瑣，將鏈表轉(zhuǎn)換成數(shù)組，并將該鏈表構(gòu)成的數(shù)組的頭和尾分別命名為left和right；
3.利用二分法尋找二叉樹搜索樹的根節(jié)點(diǎn)
代碼：
struct TreeNode *numTranslate(int *num,int left,int right)
{
? ? if(left>right)
? ? ? ? return NULL;
? ? int mid=(left+right)/2;
? ? struct TreeNode * res=(struct TreeNode *)malloc(sizeof(struct TreeNode));
? ? res->val=num[mid];
? ? res->left=numTranslate(num,left,mid-1);
? ? res->right=numTranslate(num,mid+1,right);
? ? return res;
}
struct TreeNode* sortedListToBST(struct ListNode* head){
struct ListNode *cur=head;
? ? int count=0,k=0;
? ? while(cur!=NULL)
? ? {
? ? ? ? count++;
? ? ? ? cur=cur->next;
? ? }
? ? cur=head;
? int * num=(int *)calloc(sizeof(int),count);
? ? while(cur!=NULL)
? ? {
? ? ? num[k++]=cur->val;
? ? ? ? cur=cur->next;
? ? }
return numTranslate(num,0,count-1);
}
運(yùn)行結(jié)果：
