C++ में सॉर्टेड लिस्ट को बाइनरी सर्च ट्री में बदलना

मान लीजिए हमारे पास एक सिंगली लिंक्ड लिस्ट है जहां एलिमेंट्स आरोही क्रम में सॉर्टेड हैं, हमें इसे हाइट-बैलेंस्ड BST में बदलना है। उदाहरण के लिए, अगर लिस्ट है [-10, -3, 0, 5, 9], तो संभावित ट्री होगा:

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

• अगर लिस्ट खाली है, तो नल लौटाएं

• sortedListToBST() नाम का एक रिकर्सिव मेथड डिफाइन करें जो लिस्ट का स्टार्ट नोड लेगा

• x := लिस्ट a से मिड नोड के पिछले नोड का एड्रेस

• mid := एक्जैक्ट मिड नोड

• mid के वैल्यू से वैल्यू लेकर एक नया नोड बनाएं

• nextStart := मिड नोड का नेक्स्ट

• मिड नेक्स्ट को नल सेट करें

• नोड का राइट := sortedListToBST(nextStart)

• अगर 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;
    }
};

int 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