İkili bir ağacın əvvəlcədən sifariş edilməsini yoxlayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur google
İkili ağac Qalaq AğacBaxılıb 15

Əvvəlcə a-nın əvvəlcədən nəyin əvvəlcədən sifariş edildiyini bilməliyik İkili ağac edir. Əvvəlcədən sifariş Binary Tree keçid növüdür. Əvvəlcə bu keçiddə biz nodu ziyarət edirik. Ziyarət etdikdən sonra əvvəl sol alt ağacdan sonra sağ alt ağacdan keçin. İndi bu problemdə etməli olduğumuz şeyə keçin. Bir sıra simli tip verdik. Hər bir sətrin boş nodu göstərən "#" işarəsi ola biləcəyi və ya "123" kimi sətir formatında bəzi ədədi dəyəri olduğu yerlərdə. Bizə verilən sətri tapmalıyıq ki, hər hansı bir ikili ağacdan əvvəlcədən keçməyimizdir? Hər hansı bir ikili ağacın əvvəlcədən sifarişini bildirirsə, yazdırın "Bəli" başqa çap "YOX".

İkili bir ağacın əvvəlcədən sifariş edilməsini yoxlayınPin

Bir sıra vermişiksə {"17", "5", "9", "#", "#", "15", "#", "#", "2", "#", "29" , "#", "#"}. Verilən giriş yuxarıdakı ikili ağacın əvvəlcədən əmri olduğunu söyləyə bilərik. Beləliklə çap edirik "Bəli" bizim çıxışımız kimi.

Giriş Formatı

Birinci sətirdə simli massivin uzunluğunu təyin edən tam bir N dəyəri vardır.

İkinci sətirdə ölçüsü N olan simli tipli giriş massivi var.

Çıxış formatı

Tək sətirdə çap edin "Bəli" Əgər giriş massivi hər hansı bir ikili ağacın əvvəlcədən sifarişidirsə yazdırın "YOX".

Məhdudiyyətlər

  • 1 <= N <= 100000
  • 1 <= | massiv [i] | <= 100000
Sample Input:
13
17 5 9 # # 15 # # 2 # 29 # #
Sample Output:
YES

Explanation: Giriş massivi yuxarıdakı ikili ağacın ön sifariş keçidini təmsil edir.

Burada yalnız müəyyən bir düyündəki "null" düyününün sayını hesablayırıq [i] və əgər null düyün (i null düyünlərin sayı) -dan böyükdürsə, onda birbaşa "NO" yazırıq. Burada 0 <= i <= n-1. Dizinin sonuna çatırıqsa və yuxarıdakı şərtləri yerinə yetirməsək, boş node n-düyünün boşluğunun i-sayına bərabərdirsə, "YES" yazırıq) başqa bir şəkildə "YOX" yazdırırıq. Konsepsiya sadədir, yalnız hər qovşaqda yoxlayırıq ki, boş qovşağımız bəzi dəyəri olan qovşaqlardan böyükdür.

İkili bir ağacın əvvəlcədən sifariş edilməsini yoxlayınPin

Burada bütün sıfır sayı massivini keçirik və null_count [i]> (i-null_count [i]) şərtinə cavab vermirik. Sonra sonunda yoxlayırıq null_count [n-1] == (n-1), sonra “YES” yazırıq, əksinə “YOX” yazırıq.

Yuxarıdakı null_count massivində də əvvəlki indeks dəyərindən asılı olan dəyəri artırdığımızı görürük. Beləliklə, yuxarıdakı şərti yoxlamaq üçün yalnız bir dəyişən istifadə edirik.

İkili bir ağacın ön sifariş seriyalaşdırılmasını yoxlamaq üçün alqoritm

Step:1 For i in range 0 to N-1:
       If arr[i]="#" then:
          null_count++;
       If null_count>i-null_count+2 then:
          print "NO"
Step:2 If null_count = n+1-null_count then:
          print "YES"
       Else:
          print "NO"

İkili bir ağacın ön sifariş seriyalaşdırılmasını yoxlamaq üçün tətbiqetmə

/*C++ Implementation of "Verify Preorder Serialization of a Binary Tree".*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{
    /*input values.*/
    int n;
    cin>>n;
    string arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    /*set null count to 0*/
    int null_count=0,flag=0;
    for(int i=0;i<n;i++)
    {
        /*if null node encounter then increase null_count by 1.*/
        if(arr[i]=="#")
        {
            null_count++;
        }
        /*check condition*/
        if(null_count>(i-null_count+2)&&i<n-1)
        {
            flag=1;
            cout<<"NO"<<endl;
            break;
        }
    }
    /*print result*/
    if(flag==0)
    {
        if(null_count==(n-null_count+1))
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}
11 
17 5 9 # # 15 # # 2 # #
YES

Zamanın mürəkkəbliyi

O (N) burada N - giriş massivində mövcud olan sətir sayı. Sıfır qovşaqları saymaq və vəziyyəti yoxlamaq üçün yalnız bir döngədən istifadə edirik.

Kosmik Mürəkkəblik

O (1) çünki boş qovşaqların sayını saxlamaq üçün yalnız bir dəyişən istifadə edirik. Giriş götürmək üçün istifadə olunan yer O (N) dir.

References

Translate »