//有序链表建平衡二叉树，每次取得结点可选二分法求得的中间结点，左孩子为左半部分中间结点，右孩子为右半部分中间结点，以此类推。
bitree *sortedListToBST(linklist *head,linklist *tail){//有序链表转平衡二叉树(直接转)快慢指针方法（求的链表中间结点很好用的方法）
if(head==tail){
return NULL;
}
bitree *T;
T=(bitree*)malloc(sizeof(bitree));
linklist *slow=head,*fast=head;
while(fast!=tail&&fast->next!=tail){
slow=slow->next;
fast=fast->next->next;
}
T->data=slow->data;
//printf("%d",T->data);
T->lchild=sortedListToBST(head,slow);
T->rchild=sortedListToBST(slow->next,tail);
return T;
}
bitree *sortedListToBST2(int num[],int l,int r){//数组进行建立平衡二叉树
if(l>r){
return NULL;
}
bitree *T=(bitree*)malloc(sizeof(bitree));
int mid=(l+r)/2;
T->data=num[mid];
T->lchild=sortedListToBST2(num,l,mid-1);
T->rchild=sortedListToBST2(num,mid+1,r);
return T;
}
void trans(linklist *head){//链表转化为数组
int i=0;
temp=0;
while(head->next!=NULL){
num[i++]=head->next->data;
head=head->next;
temp++;
}
}
void pre(bitree *T){
if(T){
printf("%d",T->data);
pre(T->lchild);
pre(T->rchild);
}
}
void main(){
linklist *head=create(5);
//swapPairs(head);
//reverseKGroup(head,3);
//rotateRight(head,3);
//head=deleteDuplicates2(head);
//partition(head,3);
//reverseBetween(head,1 ,4);
//bitree *T=sortedListToBST(head->next,NULL);
//pri(head);
trans(head);
bitree *T=sortedListToBST2(num,0,temp-1);
pre(T);
}
lc109-有序链表转平衡二叉树
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 1. 树结构示意图 补充： 兄弟节点：具有相同父节点的节点互称为兄弟节点。 树的深度：从根节点开始（其深度为0）自...
- 3.是否是bst的后续便利 4.二叉树转链表 5.bst转双向链表 6.第k小的元素 7.序列化8.删除bst一个点
