క్రమబద్ధీకరించిన శ్రేణిని బైనరీ శోధన చెట్టు లీట్‌కోడ్ పరిష్కారంగా మార్చండి


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది Adobe airbnb అమెజాన్ ఆపిల్ బ్లూమ్బెర్గ్ సిస్కో గూగుల్ మైక్రోసాఫ్ట్ ఒరాకిల్ Spotify VMware యాహూ
బైనరీ శోధన చెట్టు లోతు మొదటి శోధన

మనకు క్రమబద్ధీకరించబడినవి ఇవ్వండి అమరిక పూర్ణాంకాల. చెట్టు ఎత్తు-సమతుల్యతతో ఉండే విధంగా ఈ శ్రేణి నుండి బైనరీ శోధన చెట్టును నిర్మించడమే లక్ష్యం. చెట్టులోని ఏదైనా నోడ్ యొక్క ఎడమ మరియు కుడి సబ్‌ట్రీల ఎత్తు వ్యత్యాసం గరిష్టంగా 1 ఉంటే చెట్టు ఎత్తు-సమతుల్యమని చెప్పబడింది.

బహుళ పరిష్కారాలు ఉండవచ్చని కనుగొనడం సులభం. మేము ఏదైనా చెల్లుబాటు అయ్యే పరిష్కారాన్ని కనుగొనాలి. ఈ సమస్యలో, మేము చెట్టును ముద్రించాల్సిన అవసరం లేదు, కానీ ఒకదాన్ని సృష్టించడం. మేము దాని ప్రీఆర్డర్ ట్రావెర్సల్‌ను ప్రింట్ చేయాలి.

ఉదాహరణ

Array = {-4 , 0 , 1 , 2 , 7}
1 -4 0 2 7

వివరణ: BST:

క్రమబద్ధీకరించిన శ్రేణిని బైనరీ శోధన చెట్టు లీట్‌కోడ్ పరిష్కారంగా మార్చండి

 

Array = {1 , 2 , 3}
2 1 3

వివరణ: BST:

క్రమబద్ధీకరించిన శ్రేణిని బైనరీ శోధన చెట్టు లీట్‌కోడ్ పరిష్కారంగా మార్చండి

అప్రోచ్ (సూత్రం)

మేము రెండు విషయాలను ట్రాక్ చేయాలి:

  1. ఏదైనా నోడ్‌లో ఎడమ పిల్లలుగా చిన్న అంశాలు ఉండాలి మరియు కుడి పిల్లలకు విరుద్ధంగా ఉండాలి
  2. బిఎస్‌టి ఎత్తు సమతుల్యంగా ఉండాలి

ఏ క్షణంలోనైనా చెట్టును సమతుల్యంగా ఉంచడానికి, మేము శ్రేణి యొక్క మధ్య మూలకాన్ని మూలంగా ఎంచుకోవాలి. ఈ విధంగా, మనకు ఎత్తు వ్యత్యాసం ఉంటుంది 1 శ్రేణి సమాన పరిమాణం మరియు ఎత్తు వ్యత్యాసం ఉంటే ఎడమ మరియు కుడి సబ్‌ట్రీల మధ్య శ్రేణి అసమానంగా ఉన్నప్పుడు.

ఇప్పుడు, మనం ఏదైనా మిడిల్ నోడ్‌ను రూట్‌గా ఎంచుకున్నప్పుడు, ఎడమ సబ్‌ట్రే నుండి ఎడమ సబ్‌ట్రీని మరియు కుడి సబ్‌ట్రే నుండి కుడి సబ్‌ట్రీని సృష్టించాలి. ఇది మా అసలు సమస్య యొక్క ఉప సమస్య మరియు అందువల్ల మేము దానిని పునరావృతంగా పరిష్కరించగలము. మధ్య నోడ్‌కు ఎడమ మరియు కుడి సబ్‌ట్రీని కేటాయించిన తరువాత, మేము దానిని తిరిగి ఇచ్చి బైనరీ సెర్చ్ ట్రీ యొక్క పోస్టార్డర్ ట్రావెర్సల్‌ను ప్రింట్ చేయవచ్చు.

అల్గారిథం

  1. మరొక ఫంక్షన్ సృష్టించండి convertArrayToBST () ఇది ఇచ్చిన శ్రేణి యొక్క ఏదైనా నిర్దిష్ట పరిధిని మారుస్తుంది మరియు దాని సంబంధిత BST రూట్ నోడ్‌ను తిరిగి ఇస్తుంది.
  2. పైన పేర్కొన్న పరిధిలో శ్రేణి యొక్క L = ఎడమ పరిమితి మరియు శ్రేణి యొక్క R = కుడి పరిమితిని అనుమతించండి.
    1. ఉంటే L> R.
      • తిరిగి NULL, మేము తప్పు పరిధిని అందుకున్నట్లు
    2. L == R. అయితే
      • విలువను కలిగి ఉన్న క్రొత్త నోడ్‌ను తిరిగి ఇవ్వండి అర్రే [L] 
    3. ఈ పరిధి యొక్క మధ్య నోడ్‌ను కనుగొనండి mid = (L + (R - L) / 2)
      • అదే విలువతో కొత్త BST నోడ్‌గా తల ప్రారంభించండి అర్రే [మధ్య]
      • కేటాయించవచ్చు ఎడమ మరియు కుడి సబ్‌ట్రీలు వరుసగా ఎడమ మరియు కుడి ఉప-శ్రేణులలో పిలువబడతాయి
      • తిరిగి తల
  3. బైనరీ సెర్చ్ ట్రీ యొక్క ప్రీఆర్డర్ ట్రావెర్సల్‌ను ప్రింట్ చేయండి

క్రమబద్ధీకరించిన శ్రేణిని బైనరీ శోధన చెట్టు లీట్‌కోడ్ పరిష్కారానికి మార్చడం

క్రమబద్ధీకరించిన శ్రేణిని బైనరీ శోధన చెట్టుగా మార్చడానికి సి ++ పరిష్కారం

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

BSTNode* convertArrayToBST(vector <int> &a , int l , int r)
{
    if(l > r)
        return NULL;
    if(l == r)
        return new BSTNode(a[l]);
    int mid = (l + (r - l) / 2);
    BSTNode* head = new BSTNode(a[mid]);
    head->left = convertArrayToBST(a , l , mid - 1);
    head->right = convertArrayToBST(a , mid + 1 , r);
    return head;
}

BSTNode* sortedArrayToBST(vector<int>& a)
{
    int n = a.size();
    return convertArrayToBST(a , 0 , n - 1);
}

void preorder(BSTNode* head)
{
    if(!head)
        return;
    cout << head->value << " ";
    preorder(head->left);
    preorder(head->right);
}


int main()
{
    vector <int> a = {-4 , 0 , 1 , 2 , 7};
    BSTNode* head = sortedArrayToBST(a);
    preorder(head);
    return 0;
}

క్రమబద్ధీకరించిన శ్రేణిని బైనరీ శోధన చెట్టుగా మార్చడానికి జావా సొల్యూషన్

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int x)
    {
        value = x;
        left = null;
        right = null;
    }
}

class convert_array_to_BST
{
    public static void main(String args[])
    {
        int[] a = {-4 , 0 , 1 , 2 , 7};
        BSTNode head = sortedArrayToBST(a);
        preorder(head);
    }

    static BSTNode convertArrayToBST(int[] a , int l , int r)
    {
        if(l > r)
            return null;
        if(l == r)
            return new BSTNode(a[l]);
        int mid = (l + (r - l) / 2);
        BSTNode head = new BSTNode(a[mid]);
        head.left = convertArrayToBST(a , l , mid - 1);
        head.right = convertArrayToBST(a , mid + 1 , r);
        return head;
    }

    static BSTNode sortedArrayToBST(int[] a)
    {
        return convertArrayToBST(a , 0 , a.length - 1);
    }

    static void preorder(BSTNode head)
    {
        if(head == null)
            return;
        System.out.print(head.value + " ");
        preorder(head.left);
        preorder(head.right);
    }
}
1 -4 0 2 7

క్రమబద్ధీకరించిన శ్రేణిని బైనరీ సెర్చ్ ట్రీ లీట్‌కోడ్ సొల్యూషన్‌కు మార్చడం యొక్క సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

పై), N = చెట్టులోని మూలకాల సంఖ్య. మేము BST ని నిర్మించడానికి మరియు ప్రీఆర్డర్ ట్రావెర్సల్‌ను ముద్రించడానికి ప్రతి మూలకాన్ని సందర్శిస్తాము.

అంతరిక్ష సంక్లిష్టత

ఓ (హెచ్), ఇక్కడ H = చెట్టు యొక్క ఎత్తు = logN. పునరావృత ఫంక్షన్లలో, చెట్టు ఎత్తు-సమతుల్యతతో ఉందని మేము నిర్ధారించుకుంటాము, కాబట్టి, మేము గరిష్టంగా ఉపయోగిస్తాము ఓ (హెచ్) పునరావృత స్టాక్ ఫ్రేమ్‌ల కోసం స్థలం.