Проверете дали даденият масив може да представлява Преминаване по ред на ниво на двоично дърво за търсене  


Ниво на трудност Лесно
Често задавани в Амазонка Citrix IBM Наистина Info Edge OYO Стаи Терадата
Двоично дърво за търсене Двоично дърво Опашка Дърво Обръщане на дърво

Декларация за проблема  

Проблемът „Проверете дали даденият масив може да представлява обхождане на ниво ред на бинарното дърво за търсене“ гласи, че ви е дадено обръщане на ред на ниво на бинарно дърво за търсене. И използвайки обръщане на нареждане на ниво на дървото. Трябва да открием ефективно дали обхождането на нивото на реда може да представлява двоично дърво за търсене или не?

Пример  

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

 

Проверете дали даденият масив може да представлява Преминаване по ред на ниво на двоично дърво за търсенещифт

Обяснение

Даденото обръщане на ред на ниво представлява двоичното дърво, което е показано на изображението. И както виждаме, дървото отговаря на всички свойства на двоично дърво и по този начин изходът е верен.

Подход за проверка дали даденият масив може да представлява обръщане на ниво на бинарното дърво за търсене  

Наивен подход

Наивен подход би могъл да бъде, ако се опитаме да направим обръщането на всички бинарни дървета, които отговарят на дадения ред. И след това проверете дали дървото представлява двоично дърво за търсене. Но тази операция ще струва много скъпо. Както преди всичко, ще изградим много дървета. Тогава алгоритъмът изисква проверка дали формираното дърво е BST. И така, трябва да направим нещо, където не е необходимо да конструираме дървото.

Вижте също
Изтрийте N-ти възел от края на дадения свързан списък

Ефективен подход

Ефективният подход ще съхранява границите за всеки от елементите, които се срещат при обхождането на нивото. Тези граници представляват границата, в която могат да лежат техните елементи на поддървото. Ако говорим за възел, той ще има минимум и максимум. Лявото поддърво може да има елементи, вариращи от минимално обвързани до текущата стойност на възела-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

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

Сложност във времето

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

Вижте също
Намерете дублирани поддървета

Сложност на пространството

Използвали сме опашка за съхраняване на елементите, които са направили алгоритъма да има линейна пространствена сложност НА).