Праверце, ці можа дадзены масіў прадстаўляць абход парадку ўзроўню двайковага дрэва пошуку


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка 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

Аналіз складанасці

Складанасць часу

Паколькі мы проста прайшлі па стыхіі. І ў горшым выпадку нам трэба абыйсці ўсе элементы, алгарытм мае лінейную складанасць часу O (N).

Касмічная складанасць

Мы выкарыстоўвалі чаргу для захоўвання элементаў, якія зрабілі алгарытм лінейнай прасторавай складанасцю O (N).