Проверете дали дадената низа може да претставува Пресек на нарачки на ниво на стебло за бинарно пребарување


Ниво на тешкотија Лесно
Често прашувано во Амазон Citrix IBM, Навистина Инфо раб Соби OYO Teradata
Дрво за бинарно пребарување Бинарно дрво редот Дрво Преминување на дрвото

Изјава за проблем

Проблемот „Проверете дали дадената низа може да претставува Пресек на нивото на нарачката на стеблото за бинарно пребарување“ наведува дека ви е даден преглед на нивото на нарачката дрво за бинарно пребарување. И со користење на Преминување на нивото на нарачки на дрвото. Треба ефикасно да откриеме дали пресекот на нарачката за ниво може да претставува бинарно стебло за пребарување или не?

пример

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

 

Проверете дали дадената низа може да претставува Пресек на нарачки на ниво на стебло за бинарно пребарување

Објаснување

Предавањето на даденото ниво го претставува бинарното стебло што е прикажано на сликата. И, како што можеме да видиме, дрвото ги задоволува сите својства на бинарното дрво и со тоа излезот е точен.

Пристап кон проверка дали дадената низа може да претставува Пресек на нарачки на ниво на стебло за бинарно пребарување

Наивен пристап

Наивен пристап би можел да биде ако се обидеме да ги направиме сите бинарни дрвја што ја задоволуваат проверката на редоследот на даденото ниво. И потоа проверете дали дрвото претставува дрво за бинарно пребарување. Но, оваа операција ќе биде многу скапа. Како прво, ќе градиме многу дрвја. Тогаш алгоритмот бара проверка дали формираното дрво е BST. Значи, треба да направиме нешто каде што не треба да го конструираме дрвото.

Ефикасен пристап

Ефикасен пристап ќе ги зачува границите за секој од елементите што се појавуваат во пресекот на нивото. Овие граници ја претставуваат границата во која можат да лежат нивните елементи од под дрво. Ако зборуваме за јазол, тој ќе има минимум и максимум. Левото под дрво може да има елементи кои се движат од минимално врзано до моменталната вредност на јазолот-1. Додека елементите во десното под дрво можат да се движат од моменталната вредност на јазолот + 1 до максималното врзано.

Значи, ќе користиме редица каде ќе продолжиме да ги вметнуваме елементите со овие граници и ако можеме да поминуваме низ сите јазли. Ние велиме дека даденото ниво на пресек на нарачки може да претставува BST друго не. Алгоритмот е многу сличен на оној за проверка дали бинарното дрво е 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

Анализа на сложеност

Временска комплексност

Како што едноставно поминавме низ елементите. И во најлош случај, треба да ги пребродиме сите елементи, алгоритмот има линеарна сложеност во времето НА).

Комплексноста на просторот

Користевме редица за складирање на елементите што го направија алгоритмот да има линеарна просторна сложеност НА).