Sıralanmış massivi ikili axtarış ağacı leetcod həllinə çevirin

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Airbnb Amazon alma Bloomberg Cisco google microsoft Kahin Spotify VMware Yahoo
alqoritmlər İkili Axtarış Ağacı kodlaşdırma Dərinlik İlk Axtarış müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutionsBaxılıb 32

Bizə bir növ verildiyini düşünək array tam ədədi. Məqsəd bu massivdən ağacın hündürlüyü tarazlı olması üçün İkili Axtarış Ağacı yaratmaqdır. Diqqət yetirin ki, ağacdakı hər hansı bir düyünün sol və sağ alt ağaclarının hündürlüyü fərqi ən çox 1-dirsə, bir ağacın hündürlüyü balanslaşdırılmışdır.

Çoxlu həll yollarının ola biləcəyini tapmaq asandır. Etibarlı bir həll yolu tapmalıyıq. Diqqət yetirin ki, bu problemdə ağacı çap etməyə yox, bir ağac yaratmağa ehtiyacımız var. Sadəcə əvvəlcədən keçidini çap etməliyik.

misal

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

İzahat: BST:

Sıralanmış massivi ikili axtarış ağacı leetcod həllinə çevirinPin

 

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

İzahat: BST:

Sıralanmış massivi ikili axtarış ağacı leetcod həllinə çevirinPin

Yanaşma (Recursion)

İki şeyi izləməliyik:

  1. Hər hansı bir qovşaq sol uşaqlar kimi kiçik elementlərə, əksinə sağ uşaqlar üçün olmalıdır
  2. BST Boy Balanslı olmalıdır

Ağacın hər an balanslı qalması üçün kök olaraq serialın orta elementini seçməliyik. Bu şəkildə bir boy fərqimiz olacaq 1 massiv bərabər ölçülü və hündürlük fərqlidirsə, sol və sağ alt ağaclar arasında massiv oddsize olduqda.

İndi hər hansı bir orta nodu kök olaraq seçdiyimiz zaman sol alt sətirdən sol alt sətri, sağ alt sətirdən sağ alt ağacı yaratmalıyıq. Bu, orijinal problemimizin alt problemidir və buna görə də bunu təkrarən həll edə bilərik. Orta qovşağa sol və sağ alt ağac təyin etdikdən sonra geri qaytara bilərik və İkili Axtarış Ağacının postorder keçidini çap edə bilərik.

Alqoritm

  1. Başqa bir funksiya yaradın converArrayToBST () verilmiş sıra hər hansı bir xüsusi sıra çevirmək və müvafiq BST kök node qaytaracaq.
  2. Yuxarıda göstərilən aralığda L = massivin sol həddi və R = massivin sağ hüdudu olsun.
    1. Əgər L> R
      • qayıtmaq NULL, səhv bir sıra aldığımız üçün
    2. L == R
      • kimi dəyəri olan yeni bir qovşaq qaytarın Dizi [L] 
    3. Bu aralığın orta düyünü kimi tapın orta = (L + (R - L) / 2)
      • Eyni dəyəri olan yeni bir BST Node kimi başlayın Array [ortada]
      • Atayın Zamansağ eyni funksiya ilə alt ağaclar sırasıyla sol və sağ alt aralıqlara çağırıldı
      • Başını qaytarın
  3. İkili Axtarış Ağacının ön sifariş keçidini çap edin

Sıralanmış massivi ikili axtarış ağacı leetcode həllinə çevirmək

Sıralanmış massivi ikili axtarış ağacına çevirmək üçün C ++ həlli

#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;
}

Java Solution, Sortlaşdırılan Array'ı Binary Search Tree'ə çevirmək üçün

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

Sıralanmış massivi ikili axtarış ağacına aid Leetcode həllinə çevirmək üçün mürəkkəbliyin təhlili

Zamanın mürəkkəbliyi

O (N), N = Ağacdakı elementlərin sayı. BST qurmaq və əvvəlcədən sifariş keçidini çap etmək üçün hər elementi ziyarət edirik.

Kosmik Mürəkkəblik

O (H), burada H = ağacın hündürlüyü = giriş Hər iki rekursiv funksiyada da ağacın hündürlüyü tarazlı olduğundan əmin oluruq, buna görə maksimum istifadə edirik O (H) rekursiv yığın çərçivələri üçün yer.

Şərh yaz

Translate »