Санҷед, ки оё массиви додашуда метавонад пешакӣ гузаштани дарахти ҷустуҷӯи бинариро ифода кунад


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon LinkedIn
Дарахти ҷустуҷӯи бинарӣ тӯда Дарахт

Масъалаи "Санҷед, ки оё массиви додашуда метавонад пешакӣ гузаштани дарахти ҷустуҷӯи бинариро нишон диҳад" мегӯяд, ки ба шумо убури пешакӣ пайдарпаӣ Акнун ин пайдарҳамиро дида бароед ва бифаҳмед, ки оё ин пайдарпайӣ дарахти ҷустуҷӯи дутарафаро нишон дода метавонад ё не? Мураккабии интизоршудаи вақт барои ҳалли он аст О (1).

мисол

Санҷед, ки оё массиви додашуда метавонад пешакӣ гузаштани дарахти ҷустуҷӯи бинариро ифода кунад

5 3 4 7 6 9 8 11
Yes

Равиш барои санҷидани он, ки оё пайдарпаии пешакӣ BST-ро ифода мекунад

Мушкилот аз мо мепурсад, ки оё массиви додашуда метавонад пешакӣ гузаштанро ифода кунад дарахти ҷустуҷӯи бинарӣ. Ба мо як ҳамаҷониба асал ҳамчун вуруд. Акнун ба назар гиред, ки ин массив дорои a убури пешакӣ пайдарпаии дарахти ҷустуҷӯи дуӣ. Пас санҷед, ки оё пайдарпаии гузариши пешакӣ додашуда ҳатто метавонад дарахти ҷустуҷӯи бинариро нишон диҳад ё не.

Усули соддалавҳона ин аст, ки аввал унсури нисбатан бузургтар аз унсури ҳозираи рости он пайдо карда шавад. Акнун санҷед, ки оё ҳамаи элементҳои рости он аз унсури интихобшудаи ҷорӣ калонтаранд. Ва ҳамаи унсурҳои чапи элементи бузургтар ва унсури ҷории интихобшуда аз он хурдтаранд. Пас рекурсив ҳамон ҳолатро барои ҷудокунии чап аз унсури ҷорӣ ба унсури камтар аз унсури бузургтар санҷед. Ва инчунин рекурсивӣ барои зеркашӣ аз унсури бузургтар то ба охир санҷед. Ин равиш самарабахш нест, зеро барои ин мураккабии вақти O (N ^ 2) лозим аст.

Барои ҳалли масъала дар вақти хатӣ. Мо бояд онро пайдо кунем унсури бузурги оянда бо истифода аз стек. Пас, аввал стаке созед, ки арзишҳои гиреҳро нигоҳ дорад. Пас решаро ҳамчун арзиши ҳадди ақали бутун оғоз кунед. Пас аз массиви вуруди додашуда оғоз кунед. Агар мо аз болои элементе, ки аз болои стек калонтар аст, гузарем. Пас, элементҳоро тоза кунед, то даме ки стак боло шавад, агар аз элементи ҷорӣ калонтар бошад ё стек холӣ шавад. Агар шумо бо арзиши гиреҳе дучор оед, ки аз реша хурдтар бошад, пас гардиши пешакӣ дуруст нест. Дар охир вақте ки мо аз ин шароит мегузарем. Мо унсури ҷориро ба анбор тела медиҳем.

рамз

Коди 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

Таҳлили мураккабӣ

Мураккабии вақт

O (N), зеро мо аз болои тамоми нишондиҳандаҳои массиви вуруди додашуда гузаштем. Ҳамин тавр мураккабии вақт хатӣ аст.

Мураккабии фазо

O (N), зеро мо стекро истифода кардаем. Ҳамин тариқ, дар ҳолати бадтарин, мо метавонем ҳамаи гиреҳҳоро нигоҳ дорем.