BST-nin hər bir daxili qovşağında tam bir uşağın olub olmadığını yoxlayın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Accenture Amazon Monotip həllər PayPal Sinopsis
İkili Axtarış Ağacı İkili ağac AğacBaxılıb 23

Problem bəyanat

"Bir BST-nin hər bir daxili qovşağında bir uşağın olub olmadığını yoxlayın" problemi sizə ikili axtarış ağacının əvvəlcədən sifariş keçidi verildiyini bildirir. Bütün yarpaq olmayan qovşaqlarda yalnız tək bir uşaq olub olmadığını tapmaq lazımdır. Burada verilmiş girişdəki bütün qovşaqların fərqli dəyərlərə sahib olduğunu da düşünürük.

misal

BST-nin hər bir daxili qovşağında tam bir uşağın olub olmadığını yoxlayınPin

 

Preorder Traversal: 6 15 7 9 11
Yes

Explanation: Yuxarıdakı şəkildə gördüyümüz kimi, əvvəlcədən düzəldilmiş keçid olan ağacın hər daxili düyün üçün tək bir uşağı var. Beləliklə nəticə bəli.

BST-nin hər bir daxili qovşağında tam bir uşağın olub olmadığını yoxlamaq üçün yanaşma

Əvvəlcədən Traversal kökünə üstünlük verildiyini və sol və sağ alt ağacından əvvəl çap olunduğunu bildirir. Beləliklə kökündən sonrakı elementlər kökdən daha kiçik və ya daha böyükdür. Beləliklə, müəyyən bir ardıcıllığın a-nın əvvəlcədən sifariş olunduğunu yoxlamaq lazımdırsa İkili Axtarış Ağacı. Verilən ardıcıllıqla ikili axtarış ağacı yarada biləcəyimizi yoxlamaq üçün iki iç içə döngədən istifadə edə bilərik.

Sadəlövh yanaşma

Daha əvvəl müzakirə etdiyimiz kimi, əvvəlcədən sifariş keçidi yuxarıda və solda və sağda subtree yazıldıqdan sonra kök ehtiva edir. İndi bu əməliyyat edilir rekursiv olaraq ağacdakı bütün qovşaqlar örtülməyincə. Beləliklə, verilmiş ardıcıllığın bir BST-ni təmsil etdiyini yoxlaya bilərik, xarici döngənin kök götürmək üçün istifadə olunduğu iki iç içə döngəni işə salırıq. Və iç içə döngə ondan sonrakı elementlərin sol və sağ alt ağacını təmsil edə biləcəyini yoxlayır. Bunun üçün müəyyən bir indeksə qədər bütün elementlərin seçilmiş elementdən az olub olmadığını yoxlayırıq. Və bundan sonrakı elementlər seçilmiş elementdən daha böyükdür. İndi, istifadə vəziyyətimizə uyğun olaraq bu yanaşmanı dəyişdirə bilərik.

Gəlin BST-nin hər daxili düyününün tam bir uşağının olub olmadığını yoxlamaq üçün alqoritmi necə dəyişə biləcəyimizi görək. BST-nin daxili uşağının tam bir uşağı varsa. Bu o deməkdir ki, hər daxili qovşaqda sol alt ağac və ya sağ alt ağac ola bilər. Eyni anda hər iki alt ağacdan ibarət olmayacaq. Beləliklə, alqoritmimizi ümumiləşdirmək üçün. Xarici döngənin bir element seçdiyi iki iç içə döngəni istifadə edirik. Sonra iç içə döngədən sonra gələn elementlərin alt ağaclardan birinə aid olub olmadığını yoxlamaq üçün istifadə olunur. Əvvəllər əvvəllər elementlərin kökdən az olduğu, ondan sonra elementlərin ondan böyük olduğu müəyyən bir indeksimiz var idi. İndi belə bir indeks tapa bilmərik. Lakin bu metod kifayət qədər səmərəli deyil, çünki O (N ^ 2) polinom-zaman mürəkkəbliyinə malikdir.

Səmərəli yanaşma

İndiyə qədər hər hansı bir qovşaqdakı bütün uşaqların bu problemə uyğun olaraq mövcud qovşaqdan daha az və ya daha böyük olacağını bir nöqtə ilə izah etdik. Beləliklə, bir BST-nin hər bir daxili qovşağında tam bir uşağın olub olmadığını yoxlamaq üçün cari düyünün növbəti ön sifariş xələfini tapırıq. Sonra cari düyünün son ön sifariş xələfini tapırıq. Hər iki varis cari qovşaqdan az və ya cari qovşaqdan böyükdürsə. Sonra başqa bir şəkildə davam edirik ki, cari düyünün həm sol, həm də alt ağacı var, çünki elementlərdən biri cari düyündən kiçikdir. Və başqa bir düyün cari düyündən daha böyükdür. Beləliklə, tələbimizə uyğun olaraq false və ya -1 qaytarırıq.

Kodu

BST-nin hər bir daxili qovşağında tam bir uşağın olub olmadığını yoxlamaq üçün C ++ kodu

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

bool checkIfALlInternalNodesHaveSingleChild(vector<int> preorder, int i){
    int n = preorder.size();
    if(i==n-1)return true;
    int next = preorder[i+1] - preorder[i];
    int lst = preorder[n-1] - preorder[i];
    int prod = next*lst;
    if(prod<0)
    return false;
    return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
}

int main()
{
    int n;cin>>n;
    vector<int> preorder(n);
    for(int i=0;i<n;i++)cin>>preorder[i];
    cout<<(checkIfALlInternalNodesHaveSingleChild(preorder, 0) ? "Yes" : "No");
}
5
6 15 7 9 11
Yes

BST-nin hər bir daxili qovşağında tam bir uşağın olub olmadığını yoxlamaq üçün Java kodu

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  static boolean checkIfALlInternalNodesHaveSingleChild(int preorder[], int i){
      int n = preorder.length;
      if(i==n-1)return true;
      int next = preorder[i+1] - preorder[i];
      int lst = preorder[n-1] - preorder[i];
      int prod = next*lst;
      if(prod<0)
      return false;
      return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int preorder[] = new int[n];
      for(int i=0;i<n;i++)preorder[i] = sc.nextInt();
      boolean answer = checkIfALlInternalNodesHaveSingleChild(preorder, 0);
      System.out.print(answer == true ? "Yes" : "No");
  }
}
5
6 15 7 9 11
Yes

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki əvvəlcədən sifariş sırasından keçdik. Və əvvəlcədən sifariş massivində N elementi var, beləliklə xətti bir zaman mürəkkəbliyi.

Kosmik Mürəkkəblik

O (N), rekursiv yığın üçün lazım olan yer və biz də əvvəlcədən sifariş sırasını saxlamaq üçün N ölçülü bir giriş massivindən istifadə etdik.

Translate »