වර්ග කළ අරාව ද්විමය සෙවුම් ගස් ලීට්කෝඩ් විසඳුම බවට පරිවර්තනය කරන්න  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇෙබෝ Airbnb ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් සිස්කෝ ගූගල් මයික්රොසොෆ්ට් ඔරකල් Spotify VMware යාහූ
ඇල්ගොරිතම ද්විමය සෙවුම් ගස කේතීකරණය ගැඹුර පළමු සෙවීම සම්මුඛ පරීක්ෂණ සම්මුඛ සාකච්ඡා ලීට්කෝඩ් LeetCodeSolutions

අපට වර්ග කර ඇති බව සලකන්න අරාව නිඛිලවල. ගස උස සමතුලිත වන පරිදි මෙම අරාවෙන් ද්විමය සෙවුම් ගසක් තැනීම අරමුණයි. ගසෙහි ඕනෑම නෝඩයක වම් සහ දකුණු උප කුලකවල උස වෙනස උපරිම වශයෙන් 1 ක් නම් ගසක් උස සමතුලිත බව කියනු ලැබේ.

බහුවිධ විසඳුම් තිබිය හැකි බව සොයා ගැනීම පහසුය. අපි ඕනෑම වලංගු විසඳුමක් සොයා ගත යුතුයි. මෙම ගැටළුවේදී අපට ගස මුද්‍රණය කිරීමට අවශ්‍ය නොව එකක් නිර්මාණය කිරීමට අවශ්‍ය බව සලකන්න. අපට අවශ්‍ය වන්නේ එහි පූර්ව ඇණවුම් ගමන් මාර්ගය මුද්‍රණය කිරීමයි.

උදාහරණයක්  

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

පැහැදිලි කිරීම: BST යනු:

වර්ග කළ අරාව ද්විමය සෙවුම් ගස් ලීට්කෝඩ් විසඳුම බවට පරිවර්තනය කරන්නපින්

 

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

පැහැදිලි කිරීම: BST යනු:

වර්ග කළ අරාව ද්විමය සෙවුම් ගස් ලීට්කෝඩ් විසඳුම බවට පරිවර්තනය කරන්නපින්

ප්‍රවේශය (රචනය 

අපි කරුණු දෙකක් ගැන අවධානයෙන් සිටිය යුතුයි:

  1. ඕනෑම නෝඩයක වම් දරුවන් ලෙස කුඩා මූලද්‍රව්‍ය තිබිය යුතු අතර අනෙක් අතට දකුණු ළමයින් සඳහා විය යුතුය
  2. BST උස සමතුලිත විය යුතුය

ඕනෑම මොහොතක ගස සමබරව තබා ගැනීම සඳහා, අපි අරාවෙහි මැද අංගයක් මුල ලෙස තෝරා ගත යුතුය. මේ ආකාරයෙන්, අපට උස වෙනසක් ඇත 1 අරාව ඊටත් වඩා විශාල නම් සහ උසෙහි වෙනසක් තිබේ නම් වම් සහ දකුණු උප කුල අතර අරාව පරස්පර විරෝධී වන විට.

මෙයද බලන්න
ලීට්කෝඩ් විසඳුමේ බලය

දැන්, අපි ඕනෑම මැද නෝඩයක් root ලෙස තෝරා ගන්නා විට, අපට වම් උපසිරැසියෙන් වම් උප කුලකය සහ දකුණු උපසිරැසියෙන් දකුණු උප කුලකය සෑදිය යුතුය. මෙය අපගේ මුල් ගැටලුවේ උප ගැටළුවක් වන අතර එබැවින් අපට එය නැවත නැවත විසඳිය හැකිය. මැද නෝඩයට වම් සහ දකුණු උප කුලකය පැවරීමෙන් පසුව, අපට එය ආපසු ලබා දී ද්විමය සෙවුම් ගසෙහි පෝස්ටර් ඇණවුම මුද්‍රණය කළ හැකිය.

ඇල්ගොරිතම  

  1. තවත් ශ්‍රිතයක් සාදන්න convertArrayToBST () එමඟින් ලබා දී ඇති අරාවෙහි කිසියම් විශේෂිත පරාසයක් පරිවර්තනය කර එහි අනුරූපී බීඑස්ටී මූල නෝඩය නැවත ලබා දෙනු ඇත.
  2. ඉහත සඳහන් පරාසය තුළ L = වමේ අරාව සහ R = දකුණු අරාවෙහි සීමාව ඉඩ දෙන්න.
    1. නම් L> ආර්
      • ආපසු NULL, අපට වැරදි පරාසයක් ලැබෙන බැවින්
    2. L == R. නම්
      • සමාන අගයක් ඇති නව නෝඩයක් ආපසු එවන්න අරාව [එල්] 
    3. මෙම පරාසයේ මැද නෝඩය ලෙස සොයා ගන්න mid = (L + (R - L) / 2)
      • සමාන අගයක් සහිත නව BST නෝඩයක් ලෙස හිස ආරම්භ කරන්න අරාව [මැද]
      • පවරන්න වම් සහ අයිතිය උප කුලක පිළිවෙලින් වම් සහ දකුණු උප පරාසයන්හි කැඳවනු ලැබේ
      • ආපසු හිස
  3. ද්විමය සෙවුම් ගසෙහි පෙර ඇණවුම මුද්‍රණය කරන්න

ද්විමය සෙවුම් ගස් ලීට්කෝඩ් විසඳුමට වර්ග කළ අරා පරිවර්තනය කිරීම  

වර්ග කළ අරාව ද්විමය සෙවුම් ගස බවට පරිවර්තනය කිරීම සඳහා C ++ විසඳුම

#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 = ගසෙහි ඇති මූලද්‍රව්‍ය ගණන. බීඑස්ටී ඉදිකිරීමට සහ පෙර ඇණවුම් සංචලනය මුද්‍රණය කිරීමට අපි සෑම අංගයක්ම බලන්නෙමු.

මෙයද බලන්න
A + b + c = එකතුවක් වැනි විවිධ අරා තුනකින් මූලද්‍රව්‍ය තුනක් සොයා ගන්න

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (එච්), එහිදී H = ගසේ උස = logN. පුනරාවර්තන කාර්යයන් දෙකෙහිම, ගස උස සමතුලිත බව අපි සහතික කරමු, එබැවින් අපි උපරිම වශයෙන් භාවිතා කරමු ඕ (එච්) පුනරාවර්තන සිරස් රාමු සඳහා ඉඩ.