मान लीजिए कि हमारे पास एक एकल लिंक की गई सूची है जहां तत्वों को गैर-घटते क्रम में व्यवस्थित किया गया है, हमें इसे एक ऊंचाई संतुलित बाइनरी सर्च ट्री में बदलना होगा। तो अगर सूची [-10, -3, 0, 5, 9] की तरह है, तो संभावित पेड़ इस तरह होगा -
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- यदि सूची खाली है, तो
- वापसी शून्य
- एक पुनरावर्ती विधि को परिभाषित करें जिसे SortedListToBST() कहा जाता है, यह सूची प्रारंभ नोड लेगा
- x :=सूची a से मध्य नोड के पिछले नोड का पता
- मध्य :=सटीक मध्य नोड
- मध्य के मान से मान लेकर एक नया नोड बनाएं
- अगला प्रारंभ:=मध्य नोड के आगे
- अगले के मध्य को शून्य के रूप में सेट करें
- नोड का दायां:=SortedListToBST(nextStart)
- यदि x रिक्त नहीं है, तो
- x के आगे =अशक्त और नोड के बाएँ:=SortedListToBST(a)
- वापसी नोड
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
void inord(TreeNode *root){
if(root != NULL){
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
pair <ListNode*, ListNode*> getMid(ListNode* a){
ListNode* prev = NULL;
ListNode* fast = a;
ListNode* slow = a;
while(fast && fast->next){
fast = fast->next->next;
prev = slow;
slow = slow->next;
}
return {prev, slow};
}
TreeNode* sortedListToBST(ListNode* a) {
if(!a)return NULL;
pair<ListNode*, ListNode*> x = getMid(a);
ListNode* mid = x.second;
TreeNode* Node = new TreeNode(mid->val);
ListNode* nextStart = mid->next;
mid->next = NULL;
Node->right = sortedListToBST(nextStart);
if(x.first){
x.first->next = NULL;
Node->left = sortedListToBST(a);
}
return Node;
}
};
main(){
vector<int> v = {-10,-3,0,5,9};
ListNode *head = make_list(v);
Solution ob;
inord(ob.sortedListToBST(head));
} इनपुट
[-10,-3,0,5,9]
आउटपुट
-10 -3 0 5 9