وګورئ چې ورکړل شوې سرنی د بائنري لټون د ونې د کچې سپارلو کچې استازیتوب کولی شي


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon Citrix IBM په حقیقت کی د معلوماتو څنډه OYO خونه Teradata
د بائنری لټون ونه دوهم ونې په ليکه کې ونې د ونې تراشل

ستونزه بیان

ستونزه "وګورئ چې ایا ورکړل شوي صف د بائنري لټون ونې د کچې کچې لیږد وړاندیز کولی شي" په ګوته کوي چې تاسو ته د کچې کچې آرډر ټرورسل ورکول کیږي. دوه لمبري پلټنه. او د د کچې آرډر د ونې موږ اړتیا لرو په موثره توګه ومومئ که چیرې د کچې حکم ټروریسټال د بائنري لټون ونې استازیتوب کولی شي یا نه؟

بېلګه

Level Order Traversal - {5 2 7 1 6 9 }
True

 

وګورئ چې ورکړل شوې سرنی د بائنري لټون د ونې د کچې سپارلو کچې استازیتوب کولی شي

تشریح

د ورکړل شوې کچې حکم ټراسول د بائنری ونې نمایندګي کوي کوم چې په عکس کې ښودل شوي. او لکه څنګه چې موږ لیدلی شو ونې د بائنری ونې ټول ملکیتونه خوښوي او پدې توګه محصول ریښتینی دی.

لیدلو ته رسیدل که چیرې ورکړل شوي صفونه د بائنري لټون ونې د کچې کچې سپارلو نمایندګي وکړي

بې لارې چلند

یوه بیوزله لاره کیدی شي که چیرې موږ هڅه وکړو ټول بائنري ونې رامینځته کړو چې ورکړل شوي کچې امر ټرورسل پوره کړي. او بیا چیک کړئ که ونه د بائنری لټون ونې استازیتوب کوي. مګر دا عملیات به خورا ډیر لګښت ولري. د لومړي په څیر ، موږ به ډیری ونې جوړ کړو. بیا د الګوریتم چک کولو ته اړتیا لري که جوړه شوې ونه BST وي. نو ، موږ اړتیا لرو یو څه وکړو چیرې چې موږ د ونې جوړولو ته اړتیا نلرو.

اغیزمنه کړنلاره

یوه اغیزمنه کړنلاره به د هرې عنصر حدود ذخیره کړي چې د کچې کچې کچې کچې پیښې رامینځته کیږي. دا حدود هغه حد نمایش کوي په کوم کې چې د دوی فرعي برخو عناصر کولی شي دروغ وي. که موږ د نوډ په اړه وغږیږو ، نو دا به لږترلږه او اعظمي وي. کی sub فرعي وظیفه کولی شي عناصر ولري چې لږترلږه حد ته د اوسني نوډ ارزښت - 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

د جاوا کوډ چیک کولو لپاره چې ورکړل شوي صفونه د بائنري لټون ونې د کچې ټروریسټال نمایندګي کولی شي

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).