C++-এ সর্টেড লিংকড লিস্টকে ব্যালেন্সড বাইনারি সার্চ ট্রিতে রূপান্তর করা

একটি সর্টেড (নন-ডিক্রিজিং অর্ডার) সিংলি লিংকড লিস্ট দেওয়া আছে। এটিকে একটি হাইট-ব্যালেন্সড বাইনারি সার্চ ট্রি (BST) এ রূপান্তর করতে হবে। হাইট-ব্যালেন্সড মানে প্রতিটি নোডের বাম ও ডান সাবট্রির উচ্চতার পার্থক্য সর্বোচ্চ ১।

উদাহরণ

ইনপুট: [-10, -3, 0, 5, 9]

সম্ভাব্য আউটপুট ট্রি (ইনঅর্ডার ট্রাভার্সাল): -10 -3 0 5 9

সমাধানের পদ্ধতি (Recursive + Find Middle)

1. যদি লিস্ট খালি হয়, তবে NULL রিটার্ন করুন।
2. রিকারসিভ মেথড sortedListToBST(ListNode* a) ডিফাইন করুন।
3. ফাস্ট এবং স্লো পয়েন্টার ব্যবহার করে লিস্টের মিড নোড খুঁজে বের করুন (getMid ফাংশন)। এর সাথে সাথে মিড নোডের প্রিভাস নোডও রাখুন।
4. মিড নোডের ভ্যালু দিয়ে নতুন ট্রি নোড তৈরি করুন।
5. মিড নোডের নেক্সটকে nextStart হিসেবে রাখুন এবং মিড নোডের নেক্সট NULL করুন (লিস্ট ভাঙতে)।
6. ডান সাবট্রি = sortedListToBST(nextStart)।
7. যদি প্রিভাস নোড এক্সিস্ট করে (x != NULL), তবে তার নেক্সট NULL করে বাম সাবট্রি = sortedListToBST(a)।
8. ট্রি নোড রিটার্ন করুন।

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