Ստուգեք, արդյոք տվյալ զանգվածը կարող է ներկայացնել Երկուական որոնման ծառի մակարդակի կարգի անցում


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Citrix IBM Իսկապես Տեղեկատվության եզր OYO սենյակներ Տերադատա
Երկուական որոնման ծառ Երկուական ծառ Հերթ ծառ Reeառի անցում

Խնդիրի հայտարարություն

«Ստուգեք, արդյոք տվյալ զանգվածը կարող է ներկայացնել Երկուական որոնման ծառի մակարդակի կարգի անցում» խնդիրը ասում է, որ ձեզ տրված է մակարդակի կարգի անցում երկուական որոնման ծառ, Եվ օգտագործելով մակարդակի կարգի անցում ծառի Մենք պետք է արդյունավետորեն պարզենք, արդյոք մակարդակի կարգի անցումը կարող է ներկայացնել երկուական որոնման ծառ, թե ոչ:

Օրինակ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

Քանի որ մենք պարզապես անցել ենք տարրերի վրայով: Եվ ամենավատ դեպքում մենք պետք է անցնենք բոլոր տարրերը, ալգորիթմը ունի գծային ժամանակի բարդություն ՎՐԱ).

Տիեզերական բարդություն

Մենք օգտագործել ենք հերթ ՝ այն տարրերը պահելու համար, որոնք ալգորիթմը դարձրել են գծային տարածական բարդություն ՎՐԱ).