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


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Скопје
Дрво за бинарно пребарување Магацинот Дрво

Проблемот „Проверете дали дадена низа може да претставува Прелиминарно пресекување на стеблото за бинарно пребарување“ наведува дека ви е даден преверување на пресек низа. Сега разгледајте ја оваа низа и откријте дали оваа низа може да претставува бинарно стебло за пребарување или не? Очекуваната временска сложеност за решението е О (1).

пример

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

5 3 4 7 6 9 8 11
Yes

Пристап за да проверите дали низата однапред нарачана претставува BST

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

Наивен пристап е прво да се открие само поголемиот елемент од сегашниот елемент десно од него. Сега проверете дали сите елементи десно од него се поголеми од избраниот тековен елемент. И сите елементи лево од поголемиот елемент и избраниот тековен елемент се помали од него. Потоа, рекурзивно проверете ја истата состојба за левата под-низа од тековниот елемент до елемент помал од само поголемиот елемент. И исто така рекурзивно проверете ја под-низата од само поголем елемент до крајот. Овој пристап не е ефикасен затоа што за ова е потребна O (N ^ 2) сложеност во времето.

Да се ​​реши проблемот во линеарно време. Haveе мора да го најдеме следен поголем елемент користејќи оџак. Значи, прво создадете оџак кој ги чува вредностите на јазолот. Потоа иницијализирајте го коренот како минимална цел број. Потоа започнете со дадената низа за влез. Ако прегазиме елемент што е поголем од горниот дел на оџакот. Потоа продолжете да ги отстранувате елементите додека оџакот не е на врвот, ако е поголем од тековниот елемент или оџакот не стане празен. Ако наидете на вредност на јазол што е помала од коренот, тогаш пресекот на нарачката не е точен. На крајот кога ќе ги поминеме овие услови. Ние го туркаме тековниот елемент во оџакот.

Код

C ++ код за да проверите дали дадена низа може да претставува пренарачување на пресек на BST

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

bool preorderBST(int input[], int n)
{
    stack<int> s;
    int root = INT_MIN;
    for(int i=0;i<n;i++)
    {
        // if current node is smaller than the root
        // the current node lies on the right of root
        // thus it is impossible for bst
        if (input[i] < root)
            return false;
        // keep removing elements smaller than the root
        // until you find an element which is greater than the root
        while(!s.empty() && s.top()<input[i])
            root = s.top(), s.pop();
        // if current element is smaller than the root
        // push it into stack
        s.push(input[i]);
    }
    // if we passed until the end of the array
    // that means that the given preorder sequence represents a valid BST
    return true;
}

int main()
{
    int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
    int n = (sizeof input)/(sizeof input[0]);

    cout<<((preorderBST(input, n)) ? "yes" : "no");
}
yes

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

import java.util.*;

class Main{
  static boolean preorderBST(int input[], int n)
  {
      Stack<Integer> s = new Stack<Integer>();
      int root = Integer.MIN_VALUE;
      for(int i=0;i<n;i++)
      {
          // if current node is smaller than the root
          // the current node lies on the right of root
          // thus it is impossible for bst
          if (input[i] < root)
              return false;
          // keep removing elements smaller than the root
          // until you find an element which is greater than the root
          while(!s.empty() && s.peek()<input[i]){
              root = s.peek();
              s.pop();
          }
          // if current element is smaller than the root
          // push it into stack
          s.push(input[i]);
      }
      // if we passed until the end of the array
      // that means that the given preorder sequence represents a valid BST
      return true;
  }

  public static void main(String[] args)
  {
      int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
      int n = input.length;

      System.out.print((preorderBST(input, n)) ? "yes" : "no");
  }
}
yes

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

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

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

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

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