چيڪ ڪريو ته ھڪڙي ڏنل صفائي پيش ڪري سگھي ٿي بينري سرچ وڻ جي Preorder Traversal


تڪليف جي سطح آسان
بار بار پڇڻ ۾ ايڊوب Amazon LinkedIn،
ثنائي ڳولا وارو وڻ چتي وڻن

مسئلو "چيڪ ڪريو جيڪڏهن ڏنل ڏنل صفائي بائنري سرچ وڻ جي Preorder Traversal جي نمائندگي ڪري سگهي ٿي" ٻڌائي ٿي ته توهان کي هڪ ڏني وئي آهي پريڊر ٽرورس تسلسل. ھاڻي ھن تسلسل تي غور ڪريو ۽ ڳولھيو ته اھو ترتيب ھڪڙي بائنري سرچ وڻ جي نمائندگي ڪري سگھي ٿو يا نه؟ حل لاءِ متوقع وقت پيچيدگي آھي اي (1).

مثال

چيڪ ڪريو ته ھڪڙي ڏنل صفائي پيش ڪري سگھي ٿي بينري سرچ وڻ جي Preorder Traversal

5 3 4 7 6 9 8 11
Yes

چيڪ ڪرڻ جي اپ گيٽ ڪريو جيڪڏهن پري آرڊر ترتيب بي ايس ٽي جي نمائندگي ڪري ٿو

مسئلو اسان کان پڇڻ لاءِ پڇي ٿو ته ڇا ھڪڙي ڏنل ترتيب ڏيکاريل جي Preorder Traversal جي نمائندگي ڪري ٿي بائنري ڳولا وارو وڻ. اسان کي هڪ ڏنو ويو آهي انٽرويو صف انپٽ جي طور تي. ھاڻي غور ڪريو ته ھن صف ۾ ھڪڙي آھي پريڊر ٽرورس بائنري ڳولا واري وڻ جي ترتيب. پوء جانچيو ته ڏنل ڏنل پريڊر ٽراسيل ترتيب به بائنري سرچ وڻ جي نمائندگي ڪري سگهي ٿو يا نه.

هڪ غير معمولي انداز هي آهي ته پهريون صحيح عنصر حاصل ڪرڻ جي لاءِ ان ۾ صحيح عنصر کان وڌيڪ. هاڻي جانچ ڪريو ته ڇا ان جي سا allي پاسي چونڊيل موجوده عنصر کان تمام وڏا آهن. ۽ سڀني عنصرن جي کاٻي پاسي کان وڏي عنصر ۽ چونڊيل موجوده عنصر ان کان نن areو آهي. پوءِ recursively ساڳي حالت کي کاٻي ڌر کان موجوده عنصر کي هڪ عنصر کان گهٽ وڌ عنصر کان گهٽ عنصر تائين چيڪ ڪيو. ۽ پڻ ٻيهر سبري سبيليو لاءِ صرف گهڻي عنصر کان پڇي ڏسو. اهو اچڻ موثر نه آهي ڇاڪاڻ ته انهي جي لاءِ O (N ^ 2) وقت جي پيچيدگي ضروري آهي.

لڪير وقت ۾ مسئلو حل ڪرڻ. اسان کي ڳولڻ وارا پوندا اسٽيڪ استعمال ڪندي ايندڙ وڏو عنصر. تنهنڪري پهريان هڪ اسٽيڪ ٺاهيو جيڪو نوڊ جي قدرن کي محفوظ ڪري ٿو. پوءِ گھٽ ۾ گھٽ انگيز قيمت طور جڙ کي شروعات ڪريو. پوءِ شروع ڪيل انٽ جي صف سان شروع ٿيو. جيڪڏهن اسان هڪ عنصر مٿان هلون ٿا جيڪو اسٽيڪ جي چوٽي کان وڏو آهي. پوءِ عناصر کي ڪ onڻ تائين جاري رکو جيستائين اسٽيڪ مٿي هوندي آهي جيڪڏهن هاڻوڪي عنصر کان وڏو يا اسٽڪ خالي ٿي وڃي. جيڪڏھن توھان ھڪڙي نوڊ جي قيمت اچي چڪا آھيو جيڪا روٽ کان نن isي آھي ، پوء پريڊر ٽريسلر صحيح ڪونھي. آخر ۾ جڏهن اسان اهي حالتون حاصل ڪريون ٿا. اسان موجوده عنصر کي دٻڪا ۾ دٻايو.

ڪوڊ

سي ++ ڪوڊ اهو پڙتال ڪري ٿو ته ڇا ڏنل سيٽ بي ايس ٽي جي پري آرڊر ٽراسل جي نمائندگي ڪري سگهي ٿي

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

bool preorderBST(int input[], int n)
{
    stack<int> s;
    int root = INT_MIN;
    for(int i=0;i<n;i++)
    {
        // if current node is smaller than the root
        // the current node lies on the right of root
        // thus it is impossible for bst
        if (input[i] < root)
            return false;
        // keep removing elements smaller than the root
        // until you find an element which is greater than the root
        while(!s.empty() && s.top()<input[i])
            root = s.top(), s.pop();
        // if current element is smaller than the root
        // push it into stack
        s.push(input[i]);
    }
    // if we passed until the end of the array
    // that means that the given preorder sequence represents a valid BST
    return true;
}

int main()
{
    int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
    int n = (sizeof input)/(sizeof input[0]);

    cout<<((preorderBST(input, n)) ? "yes" : "no");
}
yes

جاوا ڪوڊ اهو چيڪ ڪرڻ لاءِ ته ڏنل ڏنل سيٽ BST جي Preorder traversal جي نمائندگي ڪري سگهي ٿي

import java.util.*;

class Main{
  static boolean preorderBST(int input[], int n)
  {
      Stack<Integer> s = new Stack<Integer>();
      int root = Integer.MIN_VALUE;
      for(int i=0;i<n;i++)
      {
          // if current node is smaller than the root
          // the current node lies on the right of root
          // thus it is impossible for bst
          if (input[i] < root)
              return false;
          // keep removing elements smaller than the root
          // until you find an element which is greater than the root
          while(!s.empty() && s.peek()<input[i]){
              root = s.peek();
              s.pop();
          }
          // if current element is smaller than the root
          // push it into stack
          s.push(input[i]);
      }
      // if we passed until the end of the array
      // that means that the given preorder sequence represents a valid BST
      return true;
  }

  public static void main(String[] args)
  {
      int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
      int n = input.length;

      System.out.print((preorderBST(input, n)) ? "yes" : "no");
  }
}
yes

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

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

اي (اين) ، جئين اسان ڏنل ڏنل انٽري سرڪس ۾ سڀني انڊيڪس تي چڙهائي ڪئي آهي. ان ڪري وقت جي پيچيدگي سڌي آهي.

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

اي (اين) ، ڇاڪاڻ ته اسان اسٽيڪ استعمال ڪيو آهي. اهڙي ريت بدترين حالتن ۾ ، اسان سڀ نوڊس کي اسٽور ڪري سگهون ٿا.