C++ में लिंक्ड लिस्ट को बाइनरी सर्च ट्री में बदलें - ऊंचाई संतुलित

समस्या विवरण

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

समाधान दृष्टिकोण

धीमे और तेज पॉइंटर का उपयोग करके मध्य नोड ढूंढें और पुनरावर्ती रूप से BST बनाएं:

1. यदि सूची खाली है, तो null लौटाएं
2. एक पुनरावर्ती विधि sortedListToBST() परिभाषित करें जो सूची प्रारंभ नोड लेती है
3. x := सूची a से मध्य नोड के पिछले नोड का पता
4. mid := सटीक मध्य नोड
5. मध्य के मान से एक नया नोड बनाएं
6. nextStart := मध्य नोड का अगला
7. मध्य का अगला null पर सेट करें
8. नोड का दायां := sortedListToBST(nextStart)
9. यदि x null नहीं है, तो x का अगला = null और नोड का बायां := sortedListToBST(a)
10. नोड लौटाएं

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; 
    } 
}; 

int main(){ 
    vector<int> v = {-10,-3,0,5,9}; 
    ListNode *head = make_list(v); 
    Solution ob; 
    inord(ob.sortedListToBST(head)); 
    return 0;
}

इनपुट

[-10,-3,0,5,9]

आउटपुट

-10 -3 0 5 9