ವಿಂಗಡಿಸಲಾದ ಅರೇ ಅನ್ನು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಪರಿವರ್ತಿಸಿ  


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ airbnb ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಸಿಸ್ಕೋ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ Spotify ವರೆ ಯಾಹೂ
ಅಲ್ಗಾರಿದಮ್ಗಳು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಕೋಡಿಂಗ್ ಆಳದ ಮೊದಲ ಹುಡುಕಾಟ ಸಂದರ್ಶನ ಸಂದರ್ಶನ ಪೂರ್ವಭಾವಿ ಲೀಟ್‌ಕೋಡ್ LeetCodeSolutions

ನಮಗೆ ವಿಂಗಡಿಸಲಾಗಿದೆ ಎಂದು ಪರಿಗಣಿಸಿ ಸರಣಿ ಪೂರ್ಣಾಂಕಗಳ. ಮರವು ಎತ್ತರ-ಸಮತೋಲಿತವಾಗಿರುವಂತೆ ಈ ರಚನೆಯಿಂದ ಬೈನರಿ ಹುಡುಕಾಟ ಮರವನ್ನು ನಿರ್ಮಿಸುವುದು ಗುರಿಯಾಗಿದೆ. ಮರದ ಯಾವುದೇ ನೋಡ್‌ನ ಎಡ ಮತ್ತು ಬಲ ಸಬ್‌ಟ್ರೀಗಳ ಎತ್ತರ ವ್ಯತ್ಯಾಸವು ಗರಿಷ್ಠ 1 ಆಗಿದ್ದರೆ ಮರವನ್ನು ಎತ್ತರ-ಸಮತೋಲಿತ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ.

ಬಹು ಪರಿಹಾರಗಳಿವೆ ಎಂದು ಕಂಡುಹಿಡಿಯುವುದು ಸುಲಭ. ನಾವು ಯಾವುದೇ ಮಾನ್ಯ ಪರಿಹಾರವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಾವು ಮರವನ್ನು ಮುದ್ರಿಸುವ ಅಗತ್ಯವಿಲ್ಲ ಆದರೆ ಒಂದನ್ನು ರಚಿಸಲು. ನಾವು ಅದರ ಪೂರ್ವ-ಆದೇಶದ ಅಡ್ಡಹಾಯುವಿಕೆಯನ್ನು ಮುದ್ರಿಸಬೇಕಾಗಿದೆ.

ಉದಾಹರಣೆ  

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

ವಿವರಣೆ: ಬಿಎಸ್ಟಿ:

ವಿಂಗಡಿಸಲಾದ ಅರೇ ಅನ್ನು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಪರಿವರ್ತಿಸಿಪಿನ್

 

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

ವಿವರಣೆ: ಬಿಎಸ್ಟಿ:

ವಿಂಗಡಿಸಲಾದ ಅರೇ ಅನ್ನು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಪರಿವರ್ತಿಸಿಪಿನ್

ಅನುಸಂಧಾನ (ಪುನರಾವರ್ತನೆ 

ನಾವು ಎರಡು ವಿಷಯಗಳ ಬಗ್ಗೆ ನಿಗಾ ಇಡಬೇಕು:

  1. ಯಾವುದೇ ನೋಡ್ ಎಡ ಮಕ್ಕಳಂತೆ ಸಣ್ಣ ಅಂಶಗಳನ್ನು ಹೊಂದಿರಬೇಕು ಮತ್ತು ಬಲ ಮಕ್ಕಳಿಗೆ ಪ್ರತಿಯಾಗಿರಬೇಕು
  2. ಬಿಎಸ್ಟಿ ಎತ್ತರ ಸಮತೋಲನದಲ್ಲಿರಬೇಕು

ಯಾವುದೇ ಕ್ಷಣದಲ್ಲಿ ಮರವನ್ನು ಸಮತೋಲನದಲ್ಲಿಡಲು, ನಾವು ರಚನೆಯ ಮಧ್ಯದ ಅಂಶವನ್ನು ಮೂಲವಾಗಿ ಆರಿಸಬೇಕು. ಈ ರೀತಿಯಾಗಿ, ನಾವು ಎತ್ತರ ವ್ಯತ್ಯಾಸವನ್ನು ಹೊಂದಿರುತ್ತೇವೆ 1 ರಚನೆಯು ಸಮ ಗಾತ್ರದ್ದಾಗಿದ್ದರೆ ಮತ್ತು ಎತ್ತರ ವ್ಯತ್ಯಾಸವಾಗಿದ್ದರೆ ಎಡ ಮತ್ತು ಬಲ ಸಬ್‌ಟ್ರೀಗಳ ನಡುವೆ ರಚನೆಯು ವಿಚಿತ್ರವಾದಾಗ.

ಸಹ ನೋಡಿ
ನಾಲ್ಕು ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರದ ಶಕ್ತಿ

ಈಗ, ನಾವು ಯಾವುದೇ ಮಧ್ಯಮ ನೋಡ್ ಅನ್ನು ರೂಟ್‌ನಂತೆ ಆರಿಸಿದಾಗ, ನಾವು ಎಡ ಸಬ್‌ಟ್ರೇ ಅನ್ನು ಎಡ ಸಬ್‌ರೇರ್‌ನಿಂದ ಮತ್ತು ಬಲ ಸಬ್‌ಟ್ರೀ ಅನ್ನು ಬಲ ಸಬ್‌ರೇರ್‌ನಿಂದ ರಚಿಸಬೇಕು. ಇದು ನಮ್ಮ ಮೂಲ ಸಮಸ್ಯೆಯ ಉಪ-ಸಮಸ್ಯೆಯಾಗಿದೆ ಮತ್ತು ಆದ್ದರಿಂದ ನಾವು ಅದನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಪರಿಹರಿಸಬಹುದು. ಮಧ್ಯದ ನೋಡ್‌ಗೆ ಎಡ ಮತ್ತು ಬಲ ಸಬ್‌ಟ್ರೀ ಅನ್ನು ನಿಯೋಜಿಸಿದ ನಂತರ, ನಾವು ಅದನ್ನು ಹಿಂತಿರುಗಿಸಬಹುದು ಮತ್ತು ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀನ ಪೋಸ್ಟಾರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ಮುದ್ರಿಸಬಹುದು.

ಕ್ರಮಾವಳಿ  

  1. ಮತ್ತೊಂದು ಕಾರ್ಯವನ್ನು ರಚಿಸಿ convertArrayToBST () ಇದು ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯ ಯಾವುದೇ ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯನ್ನು ಪರಿವರ್ತಿಸುತ್ತದೆ ಮತ್ತು ಅದರ ಅನುಗುಣವಾದ ಬಿಎಸ್ಟಿ ರೂಟ್ ನೋಡ್ ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ.
  2. ಮೇಲೆ ತಿಳಿಸಿದ ವ್ಯಾಪ್ತಿಯಲ್ಲಿ L = ಎಡ ಶ್ರೇಣಿಯ ರಚನೆ ಮತ್ತು ರಚನೆಯ R = ಬಲ ಮಿತಿಯನ್ನು ಬಿಡಿ.
    1. ಎಲ್> ಆರ್ ಆಗಿದ್ದರೆ
      • ರಿಟರ್ನ್ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು, ನಾವು ತಪ್ಪು ಶ್ರೇಣಿಯನ್ನು ಸ್ವೀಕರಿಸಿದಂತೆ
    2. ಎಲ್ == ಆರ್ ಆಗಿದ್ದರೆ
      • ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ಹೊಸ ನೋಡ್ ಅನ್ನು ಹಿಂತಿರುಗಿ ಅರೇ [ಎಲ್] 
    3. ಈ ಶ್ರೇಣಿಯ ಮಧ್ಯದ ನೋಡ್ ಅನ್ನು ಹುಡುಕಿ ಮಧ್ಯ = (ಎಲ್ + (ಆರ್ - ಎಲ್) / 2)
      • ಹೊಸ ಬಿಎಸ್‌ಟಿ ನೋಡ್‌ನಂತೆ ತಲೆಯನ್ನು ಪ್ರಾರಂಭಿಸಿ ಅರೇ [ಮಧ್ಯ]
      • ನಿಗದಿಪಡಿಸಿ ಬಿಟ್ಟು ಮತ್ತು ಬಲ ಸಬ್‌ಟ್ರೀಗಳು ಕ್ರಮವಾಗಿ ಎಡ ಮತ್ತು ಬಲ ಉಪ-ಶ್ರೇಣಿಗಳಲ್ಲಿ ಕರೆಯಲ್ಪಡುವ ಅದೇ ಕಾರ್ಯ
      • ಹಿಂತಿರುಗಿ ತಲೆ
  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 = ಮರದ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಬಿಎಸ್ಟಿ ನಿರ್ಮಿಸಲು ಮತ್ತು ಪ್ರಿ-ಆರ್ಡರ್ ಟ್ರಾವೆರ್ಸಲ್ ಅನ್ನು ಮುದ್ರಿಸಲು ನಾವು ಪ್ರತಿ ಅಂಶವನ್ನು ಭೇಟಿ ಮಾಡುತ್ತೇವೆ.

ಸಹ ನೋಡಿ
ಎ + ಬಿ + ಸಿ = ಮೊತ್ತದ ವಿಭಿನ್ನ ಮೂರು ಅರೇಗಳಿಂದ ಮೂರು ಎಲಿಮೆಂಟ್ ಅನ್ನು ಹುಡುಕಿ

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎಚ್), ಅಲ್ಲಿ H = ಮರದ ಎತ್ತರ = ಲಾಗ್ ಎನ್. ಪುನರಾವರ್ತಿತ ಎರಡೂ ಕಾರ್ಯಗಳಲ್ಲಿ, ಮರವು ಎತ್ತರ-ಸಮತೋಲಿತವಾಗಿದೆ ಎಂದು ನಾವು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳುತ್ತೇವೆ, ಆದ್ದರಿಂದ, ನಾವು ಗರಿಷ್ಠವನ್ನು ಬಳಸುತ್ತೇವೆ ಒ (ಎಚ್) ಪುನರಾವರ್ತಿತ ಸ್ಟಾಕ್ ಫ್ರೇಮ್‌ಗಳಿಗೆ ಸ್ಥಳ.