Берилген массив экилик издөө дарагынын деңгээлинин өтүшүн көрсөтө алаарын текшерип алыңыз


Кыйынчылык деңгээли жеңил
Көп суралган Amazon Citrix IBM Чындыгында Info Edge OYO бөлмөлөр Терадата
Binary Search Tree Binary Tree кезек дарак Tree Traversal

Маселени билдирүү

"Берилген массив экилик издөө дарагынын деңгээлинин өтүшүн көрсөтө алабы же жокпу, текшерип көрүңүз" деген маселе сизге экилик издөө дарагы. Жана деңгээлдин өтүшү дарактын. Деңгээлдин өтүшү экилик издөө дарагын көрсөтө алабы же жокпу, натыйжалуу табышыбыз керекпи?

мисал

Level Order Traversal - {5 2 7 1 6 9 }
True

 

Берилген массив экилик издөө дарагынын деңгээлинин өтүшүн көрсөтө алаарын текшерип алыңыз

түшүндүрүү

Берилген деңгээлдин өтүшү сүрөттө көрсөтүлгөн экилик даракты билдирет. Көрүнүп тургандай, дарак экилик дарактын бардык касиеттерин канааттандырат, демек, жыйынтыгы чын.

Берилген массив экилик издөө дарагынын деңгээлинин өтүшүн көрсөтө алабы, жокпу, текшерүү ыкмасы

Naive Appocach

Берилген деңгээлдеги тартипти канааттандырган экилик бак-дарактардын бардыгын трансляциялоого аракет жасасак, анда аң-сезимсиз мамиле болушу мүмкүн. Андан кийин дарак экилик издөө дарагын чагылдыргандыгын текшериңиз. Бирок бул операция абдан кымбатка турат. Баарынан мурда, биз көптөгөн бак-дарактарды курабыз. Андан кийин алгоритм түзүлгөн бактын BST экендигин текшерүүнү талап кылат. Демек, биз бакты куруунун кереги жок жерде бир нерсе жасашыбыз керек.

Натыйжалуу мамиле

Натыйжалуу ыкма деңгээлдин өтүшүндө пайда болгон элементтердин ар биринин чектерин сактайт. Бул чектер алардын субтрак элементтери жайгашкан чек араны билдирет. Эгер түйүн жөнүндө сөз кыла турган болсок, ал минималдуу жана максималдуу болот. Сол subtree минималдуу байланышкан учурдагы түйүн мааниси-1 чейин элементтерге ээ болушу мүмкүн. Оң subtree элементтери учурдагы түйүн маанисинен + 1 максималдуу чекке чейин өзгөрүшү мүмкүн.

Ошентип, биз элементтерди ушул чектер менен киргизе турган кезекти колдонобуз жана эгерде биз бардык түйүндөрдү аралай алсак. Берилген деңгээлдин буйругу менен өтүү БСТны көрсөтпөсө болот, башкача айтканда. Алгоритм экилик дарактын BST экендигин же жок экендигин текшергенге абдан окшош?

коду

Берилген массивдин бинардык издөө дарагынын деңгээлинин өтүшүн көрсөтө алаарын текшерүү үчүн C ++ коду

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

struct node{
    int data;
    int mn;
    int mx;
};

node create(int data, int mn, int mx){
    node tmp;
    tmp.data = data;
    tmp.mn = mn;
    tmp.mx = mx;
    return tmp;
}

bool checkLevelOrderTraversalRepresentBinarySearchTree(vector<int> traversal){
    queue<node> q;
    int i = 0, n = traversal.size();
    q.push(create(traversal[i++], INT_MIN, INT_MAX));

    while(!q.empty()){
        node now = q.front();
        q.pop();
        if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
            q.push(create(traversal[i++], now.mn, now.data));
        if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
            q.push(create(traversal[i++], now.data, now.mx));
    }
    return (i == n);
}

int main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int> traversal(n);
        for(int i=0;i<n;i++)
            cin>>traversal[i];
        cout<<(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no")<<endl;
    }
}
1
6
5 2 7 1 6 9
true

Берилген массив бинардык издөө дарагынын деңгээлинин өтүшүн көрсөтө алабы же жокпу текшерүү үчүн Java коду

import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  int mn;
  int mx;
}

class Main{
  
  static node create(int data, int mn, int mx){
      node tmp = new node();
      tmp.data = data;
      tmp.mn = mn;
      tmp.mx = mx;
      return tmp;
  }
  
  static boolean checkLevelOrderTraversalRepresentBinarySearchTree(int traversal[]){
      Queue<node> q = new LinkedList<node>();
      int i = 0; int n = traversal.length;
      q.add(create(traversal[i++], Integer.MIN_VALUE, Integer.MAX_VALUE));
  
      while(q.size() > 0){
          node now = q.peek();
          q.remove();
          if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
              q.add(create(traversal[i++], now.mn, now.data));
          if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
              q.add(create(traversal[i++], now.data, now.mx));
      }
      return (i == n);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int t = sc.nextInt();
      while(t-- > 0){
          int n = sc.nextInt();
          int[] traversal = new int[n];
          for(int i=0;i<n;i++)
              traversal[i] = sc.nextInt();
          System.out.println(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no");
      }
  }
}
1
6
5 2 7 1 6 9
true

Комплекстик анализ

Убакыт татаалдыгы

Биз жөн эле элементтердин арасынан өтүп кеткендей. Жана эң начар учурда, биз бардык элементтерди басып өтүшүбүз керек, алгоритм убакыттын сызыктуу татаалдыгына ээ O (N).

Космостун татаалдыгы

Алгоритмди сызыктуу мейкиндик татаалдыгына ээ кылган элементтерди сактоо үчүн кезек колдондук O (N).