सी ++ में क्रमबद्ध सूची को बाइनरी सर्च ट्री में कनवर्ट करें

मान लीजिए कि हमारे पास एक एकल लिंक की गई सूची है जहां तत्वों को आरोही क्रम में क्रमबद्ध किया गया है, हमें इसे ऊंचाई संतुलित बीएसटी में बदलना होगा। तो अगर सूची [-10, -3, 0, 5, 9] की तरह है, तो संभावित पेड़ इस तरह होगा -

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• यदि सूची खाली है, तो शून्य वापस लौटें

• SortedListToBST () नामक एक पुनरावर्ती विधि को परिभाषित करें, यह सूची प्रारंभ नोड लेगा

• x :=सूची a से मध्य नोड के पिछले नोड का पता

• मध्य:=सटीक मध्य नोड

• मध्य के मान से मूल्य लेकर एक नया नोड बनाएं

• अगला प्रारंभ :=मध्य नोड के आगे

• अगले मध्य को शून्य के रूप में सेट करें

• नोड का अधिकार:=सॉर्ट किया गया लिस्ट टूबीएसटी (अगला प्रारंभ)

• यदि x शून्य नहीं है, तो x के बगल में =शून्य और नोड के बाईं ओर:=SortedListToBST(a)

• वापसी नोड

उदाहरण (C++)

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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