چڪاس ڪريو ته ڇا بي ٽي ايس جي هر اندروني نوڊ جو هڪ ئي ٻار آهي


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Accenture Amazon مونوٽائپ حل PayPal ڪنڊوزس
ثنائي ڳولا وارو وڻ بائنري وڻ وڻن

مسئلي جو بيان

"چڪاس ڪريو ته ڇا بي ٽي ايس جي هر اندروني نوڊ جو هڪ ئي ٻار آهي" مسئلو ٻڌائي ٿو ته توهان کي بائنري سرچ وڻ جي اڳين آرڊر ٽراول ڏنو ويو آهي. ۽ توهان کي ڳولڻ جي ضرورت آهي ته سڀ غير-پتي نوڊس ۾ صرف هڪ ٻار شامل آهي. هتي اسان اهو پڻ غور ڪيو ته ڏنل ڏنل انڊر ۾ سڀ جوڙيون ڌار قدر آهن.

مثال

چڪاس ڪريو ته ڇا بي ٽي ايس جي هر اندروني نوڊ جو هڪ ئي ٻار آهي

 

Preorder Traversal: 6 15 7 9 11
Yes

وضاحت: جئين اسان مٿي theاڻايل تصوير ۾ ڏسي سگهون ٿا ، ڏنل وڻ جنهن ۾ ڏنل پريڊر ٽراسيل آهي ، هر اندروني نوڊ لاءِ هڪڙو هڪڙو ٻار آهي. اھڙي طرح ٻاھر آھي ھا.

اهو جاچ پڙتال ڪريو ته هر بي ٽي ايس جو اندروني نوڊ بلڪل هڪ ٻار آهي

Preorder ٽرانسورس مطلب ته روٽ کي ترجيح ڏني وئي آهي ۽ ان جي کاٻي ۽ سا subي سبتري کان اڳ ڇپيل آهي. اهڙي طرح پاڙ کان پوءِ عنصر نن eitherا هوندا آهن يا روٽ کان وڏا هوندا آهن. سو ، جيڪڏهن اسان کي چڪاس ڪرڻو پوندو ته هڪ ڏنل تسلسل الف جي پهرين صورت آهي ثنائي ڳولا وارو وڻ. اسان ٻه جانچ ٿيل لَپس استعمال ڪري جانچ ڪري سگھون ٿا ته ڇا اسان ڏنل تسلسل سان بائنري سرچ وڻ ٺاهي سگهون ٿا.

نائي اچڻ وارو

جيئن ته اسان اڳ ۾ ئي بحث ڪري چڪا آهيون ، اها پهرين آرڊر ٽرائيسل مٿي کان هيٺ واري پاسي هوندي آهي ۽ کاٻي ۽ سا subي سبري ڇپجڻ کان پوءِ. ھاڻي ھي آپريشن ٿي چڪو آھي ٻيهر جيستائين وڻ ۾ سڀ نوڙيون areڪيل نه ٿينديون. تنهن ڪري ، اسان چيڪ ڪري سگهون ٿا ته ڏنل تسلسل بي ايس ٽي جي نمائندگي ڪري ٿو ، اسين ٻه گهرايل لوپ هلائيندا آهيون جتي ٻاهرين لوپ کي روٽ چونڊڻ لاءِ استعمال ڪيو ويندو آهي. ۽ ديبل ٿيل لوپ چيڪ ڪندو آهي ته ان جا عنصر ان جي کاٻي ۽ سا subي سبت جي نمائندگي ڪري سگھن. ان لاءِ ، اسان چڪاسون ٿا ته جيستائين هڪ خاص انڊيڪس سڀئي عنصر چونڊيل عنصر کان گهٽ نه هوندا. ۽ ان کانپوءِ عنصر چونڊيل عنصر کان وڌيڪ هوندا آهن. هاڻ ، اسان هن طريقيڪار کي اسان جي استعمال واري ڪيس جي مطابق تبديل ڪري سگهون ٿا.

اچو ته ڏسو ته اسان ڪيئن جانچ ڪري الگورتھم کي تبديل ڪري سگھون ٿا ته ڇا بي ٽي ايس جي هر اندروني نوڊ جو هڪ ئي ٻار آهي. جيڪڏهن بي ايس ٽي جي اندرين ٻار کي هڪ ئي ٻار آهي. ان جو مطلب آھي ته ھر اندروني نوڊ کي ڇڏي سگھجي ٿو يا ته ڇڏي ويو گھٽ ذيلي يا صحيح سبٽيري. اهو هڪ ئي وقت ۾ ذيلي ذخيرو شامل نه ڪندو. اهڙي طرح ، اسان جي الگورتھم کي مختصر ڪرڻ لاءِ. اسان ٻه جوڙيل لوپ استعمال ڪندا آهيون ، جتي ٻاهرين لوپ هڪ عنصر چونڊي ٿي. تنهن کان پوءِ جوڙيل حوض کي جانچڻ لاءِ استعمال ڪيو ويندو آهي ته آيا عناصر اچڻ کانپوءِ اهو ڪنهن ذيلي ذخيرو جي ڪنهن سان تعلق رکي ٿو. اڳي ، اسان وٽ ھڪڙو خاص انڊيڪس ھلندو ھو جنھن کان اڳ عناصر روٽ کان گھٽ ، بعد ۾ عناصر ان کان وڏا ھوندا ھئا. ھاڻي ، اسان اھڙي ڪا انڊيڪس نه ڳولينداسين. پر اهو طريقو ڪافي ڪارائتو نه آهي ڇاڪاڻ ته هن کي O (N ^ 2) جي پولينوميل ٽائيم وقت جي پيچيدگي آهي.

سگهارو انداز

هينئر تائين ، اسان هڪ نقطو واضح ڪيو آهي ته ڪنهن به نوڊ جي سمورن ٻارن ، انهي مسئلي وانگر هاڻوڪي نوڊ کان نن eitherو يا وڏو هوندو. تنهن ڪري ، اهو جانچڻ لاءِ ته ڇا بي ايس ٽي جو هر اندروني نوڊ جو هڪ ئي ٻار آهي ، اسان موجوده نوڊ جو اڳيون اڳيون جانشين ڏيون ٿا. ان کان پوء اسان کي موجوده نوڊ جو آخري اڳئين جانشين ملندي آهي. جيڪڏھن ٻئي جانشين موجوده نوڊ کان گھٽ يا موجوده نوڊ کان وڌيڪ گھٽ آھن. ان کان پوء اسين اڳتي وڌون ٿا اسان thatاڻون ٿا ته موجوده نوڊ کي کاٻي ۽ سا subي ٻئي جون آهن ڇو ته هڪ عنصر موجوده نوڊ کان نن isو آهي. ۽ ٻيو نوڊ موجوده نوڊ کان وڏو آهي. اهڙيءَ ريت اسان پنهنجي ضرورت مطابق غلط يا -1 موٽيو ٿا.

ڪوڊ

C ++ ڪوڊ اهو جانچڻ لاءِ ته ڇا بي ايس ٽي جو هر اندروني نوڊ جو هڪ ئي ٻار آهي

#include<bits/stdc++.h>
using namespace std;

bool checkIfALlInternalNodesHaveSingleChild(vector<int> preorder, int i){
    int n = preorder.size();
    if(i==n-1)return true;
    int next = preorder[i+1] - preorder[i];
    int lst = preorder[n-1] - preorder[i];
    int prod = next*lst;
    if(prod<0)
    return false;
    return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
}

int main()
{
    int n;cin>>n;
    vector<int> preorder(n);
    for(int i=0;i<n;i++)cin>>preorder[i];
    cout<<(checkIfALlInternalNodesHaveSingleChild(preorder, 0) ? "Yes" : "No");
}
5
6 15 7 9 11
Yes

جاوا ڪوڊ اهو جاچڻ لاءِ ته ڇا بي ايس ٽي جو هر اندروني نوڊ جو هڪ ئي ٻار آهي

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  static boolean checkIfALlInternalNodesHaveSingleChild(int preorder[], int i){
      int n = preorder.length;
      if(i==n-1)return true;
      int next = preorder[i+1] - preorder[i];
      int lst = preorder[n-1] - preorder[i];
      int prod = next*lst;
      if(prod<0)
      return false;
      return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int preorder[] = new int[n];
      for(int i=0;i<n;i++)preorder[i] = sc.nextInt();
      boolean answer = checkIfALlInternalNodesHaveSingleChild(preorder, 0);
      System.out.print(answer == true ? "Yes" : "No");
  }
}
5
6 15 7 9 11
Yes

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين) ، ڇاڪاڻ ته اسان صرف اڳئين ترتيب جي ذريعي گھرايو آهي. ۽ پري آرڊر صف ۾ اين عنصر آهن اهڙي ريت هڪ لڪير وقت جي پيچيدگي

خلائي پيچيدگي

اي (اين) ، خلا واري اسٽوري لاءِ گهربل جڳهه ، ۽ اسان پري آرڊر جي ترتيب کي اسٽور ڪرڻ لاءِ سائز اين جي هڪ ان پٽ صف پڻ استعمال ڪئي.