Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Sponsored: https://www.wanderful.io has published a chatbot, who can chat with you and help you find apartments in San Francisco and Bay area. Check it out: http://m.me/wanderful.io
C++:
01 Node* buildBST(ListNode* head)
02 {
03 if(head==NULL)
04 return NULL;
05 Node* hd=new Node;
06 if(head->next==NULL){
07 hd->value=head->value;
08 hd->left=NULL;
09 hd->right=NULL;
10 return hd;
11 }
12 ListNode* tmp=head;
13 ListNode* prv=head;
14 for(ListNode* test=head;test!=NULL;prv=tmp,tmp=tmp->next){
15 test=test->next;
16 if(test==NULL)
17 break;
18 test=test->next;
19 }
20 prv->next=NULL;
21 hd->value=tmp->value;
22 hd->left=buildBST(head);
23 hd->right=buildBST(tmp->next);
24 return hd;
25 }
02 {
03 if(head==NULL)
04 return NULL;
05 Node* hd=new Node;
06 if(head->next==NULL){
07 hd->value=head->value;
08 hd->left=NULL;
09 hd->right=NULL;
10 return hd;
11 }
12 ListNode* tmp=head;
13 ListNode* prv=head;
14 for(ListNode* test=head;test!=NULL;prv=tmp,tmp=tmp->next){
15 test=test->next;
16 if(test==NULL)
17 break;
18 test=test->next;
19 }
20 prv->next=NULL;
21 hd->value=tmp->value;
22 hd->left=buildBST(head);
23 hd->right=buildBST(tmp->next);
24 return hd;
25 }
A better solution: Build the tree recursively using an in-order traverse.
C++:
01 Node* buildBSTbetter(ListNode*& head,int start,int end)
02 {
03 if(start>end)
04 return NULL;
05 int middle=(start+end)/2;
06 Node* left_tree=buildBSTbetter(head, start, middle–1);
07 Node* hd=new Node;
08 hd->value=head->value;
09 head=head->next;
10 Node* right_tree=buildBSTbetter(head,middle+1,end);
11 hd->left=left_tree;
12 hd->right=right_tree;
13 return hd;
14 }
02 {
03 if(start>end)
04 return NULL;
05 int middle=(start+end)/2;
06 Node* left_tree=buildBSTbetter(head, start, middle–1);
07 Node* hd=new Node;
08 hd->value=head->value;
09 head=head->next;
10 Node* right_tree=buildBSTbetter(head,middle+1,end);
11 hd->left=left_tree;
12 hd->right=right_tree;
13 return hd;
14 }
Advertisements