БСТ-ийн дотоод зангилаа бүр яг нэг хүүхэдтэй эсэхийг шалгана уу


Хэцүү байдлын түвшин Easy
Байнга асуудаг Accenture Амазоны Монотип шийдэл PayPal Синопсис
Хоёртын хайлтын мод Хоёртын мод Мод

Асуудлын мэдэгдэл

“BST-ийн дотоод зангилаа тус бүрт яг нэг хүүхэд байгаа эсэхийг шалга” гэсэн асуудалд танд хоёртын хайлтын модны урьдчилсан захиалга өгөхийг зааж өгсөн болно. Бүх навчны бус зангилаанууд зөвхөн ганц хүүхэд агуулдаг эсэхийг олж мэдэх хэрэгтэй. Энд өгөгдсөн оролтын бүх зангилаа нь ялгаатай утгатай гэж бид үзэж байна.

Жишээ нь

БСТ-ийн дотоод зангилаа бүр яг нэг хүүхэдтэй эсэхийг шалгана уу

 

Preorder Traversal: 6 15 7 9 11
Yes

Тайлбар: Дээрх зурган дээрээс харахад урьдчилсан байдлаар хөндлөн огтлолцсон мод нь дотоод зангилаа тус бүрт нэг хүүхэдтэй байдаг. Тиймээс гаралт тийм байна.

БСТ-ийн дотоод зангилаа бүр яг нэг хүүхэдтэй эсэхийг шалгах арга

Урьдчилсан захиалга үндэс нь давуу эрх олгож, зүүн, баруун дэд модных нь өмнө хэвлэнэ гэсэн үг юм. Тиймээс язгуурын дараах элементүүд нь язгуураас бага эсвэл том байна. Тиймээс хэрэв өгөгдсөн дараалал нь а-ийн урьдчилсан захиалга мөн эсэхийг шалгах шаардлагатай бол Хоёртын хайлтын мод. Өгөгдсөн дарааллаар хоёртын хайлтын мод үүсгэж болох эсэхийг шалгахын тулд бид хоёр үүрлэсэн гогцоог ашиглаж болно.

Гэнэн хандлага

Бид өмнө нь ярилцсанчлан урьдчилсан захиалга нь дээд ба зүүн, баруун дэд модыг хэвлэсний дараа язгуурыг агуулдаг. Одоо энэ ажиллагаа хийгдлээ рекурсив байдлаар модны бүх зангилаа бүрхэгдсэн хүртэл. Өгөгдсөн дараалал нь BST-г илэрхийлж байгаа эсэхийг шалгаж болох бөгөөд гаднах гогцоог үндэс сонгоход ашигладаг хоёр гогцоог ажиллуулна. Дотор гогцоо нь түүний зүүн ба баруун дэд модыг төлөөлж чадах эсэхийг шалгана. Үүний тулд тодорхой индекс хүртэл бүх элементүүд сонгосон элементээс бага байх эсэхийг шалгана. Үүний дараа элементүүд нь сонгосон элементээс их байна. Одоо бид энэхүү хандлагыг хэрэглээнийхээ дагуу өөрчилж болно.

BST-ийн дотоод зангилаа бүр яг нэг хүүхэдтэй эсэхийг шалгахын тулд алгоритмыг хэрхэн өөрчилж болохыг үзье. Хэрэв БСТ-ийн дотоод хүүхэд яг нэг хүүхэдтэй бол. Энэ нь дотоод зангилаа бүр зүүн эсвэл баруун дэд модтой байж болно гэсэн үг юм. Энэ нь хоёр дэд модыг зэрэг агуулахгүй. Тиймээс, бидний алгоритмыг нэгтгэн дүгнэх. Бид гаднах гогцоо нь элементийг сонгодог хоёр үүрлэсэн гогцоог ашигладаг. Дараа нь үүрлэсэн гогцоо нь дараахь элементүүд дэд модны аль нэгэнд хамааралтай эсэхийг шалгахад хэрэглэгддэг. Өмнө нь бид өмнө нь элементүүд язгуураас бага, дараа нь элементүүд түүнээс их байх тодорхой индекстэй байсан. Одоо ийм индекс олдохгүй байна. Гэхдээ энэ арга нь O (N ^ 2) -ийн олон гишүүнт хугацааны нарийн төвөгтэй тул хангалттай үр дүнтэй биш юм.

Үр ашигтай арга

Өнөөг хүртэл бид энэ асуудлын дагуу аль ч зангилааны бүх хүүхдүүд одоогийн зангилаанаас бага эсвэл том байх болно гэдгийг нэг цэг дээр тодорхой хэлсээр ирсэн. Тиймээс BST-ийн дотоод зангилаа бүр яг нэг хүүхэдтэй эсэхийг шалгахын тулд одоогийн зангилааны дараагийн захиалагч залгамжлагчийг олох болно. Дараа нь бид одоогийн зангилааны сүүлчийн захиалагчийн залгамж халааг олно. Хэрэв залгамжлагч хоёулаа одоогийн зангилаанаас бага буюу одоогийн зангилаанаас их байвал. Элементүүдийн аль нэг нь одоогийн зангилаанаас бага тул одоогийн зангилаа зүүн ба баруун дэд модтой болохыг бид дахин мэднэ. Өөр нэг зангилаа одоогийн зангилаанаас том байна. Тиймээс бид шаардлагын дагуу худал эсвэл -1 буцааж өгдөг.

код

BST-ийн дотоод зангилаа бүр яг нэг хүүхэдтэй эсэхийг шалгах C ++ код

#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-ийн дотоод зангилаа бүр яг нэг хүүхэдтэй эсэхийг шалгах Java код

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

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), бид дөнгөж урьдчилж захиалах массивыг дайран өнгөрөв. Урьдчилан захиалах массив нь N элементтэй тул цаг хугацааны нарийн төвөгтэй байдал юм.

Сансрын нарийн төвөгтэй байдал

O (N), рекурсив стекэд шаардлагатай зай, мөн урьдчилж захиалах дарааллыг хадгалахын тулд N хэмжээтэй оролтын массив ашигласан.