Өгөгдсөн массив нь хоёртын хайлтын модны түвшингийн дарааллыг илэрхийлж чадах эсэхийг шалгана уу


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны 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).