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


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ایڈوب ترلاسه کړئ Amazon LinkedIn
د بائنری لټون ونه د دلۍ ونې

ستونزه "وګورئ چې ایا ورکړل شوی صف کولی شي د بائنري لټون ونې د پیژندنې مخه ونیسي" بیانوي چې تاسو ته ورکړل شوی د سپارنې مخه ترتیب. اوس دې تسلسل ته پام وکړئ او ومومئ چې ایا دا ترتیب د بائنری لټون ونې نمایندګي کولی شي که نه؟ د حل لپاره تمه شوي وخت پیچلتیا ده O (1).

بېلګه

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

5 3 4 7 6 9 8 11
Yes

لیدو لپاره لیدو که چیرې د پری آرډر ترتیب د BST استازیتوب کوي

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

یوه نابغه لاره دا ده چې لومړی د هغې په ښي اړخ کې د اوسني عنصر څخه خورا لوی عنصر ومومئ. اوس وګورئ چې ایا د هغې په ښي خوا کې ټول عناصر د غوره شوي اوسني عنصر څخه لوی دي. او د لوی عنصر په کی left کې ټول عناصر او غوره شوي اوسني عنصر له دې څخه کوچني دي. بیا په تکراري ډول د اوسني عنصر څخه تر عنصر پورې د کی greaterې سبرای لپاره ورته حالت چیک کړئ چې د خورا لوی عنصر څخه لږ دی. او همدارنګه په تکرار سره د زیاتو عنصر څخه تر پای پورې د فرعي لټون وکړئ. دا چلند مؤثر ندی ځکه چې دا د O (N ^ 2) وخت پیچلتیا ته اړتیا لري.

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

کوډ

C ++ کوډ چیک کولو لپاره چې ایا ورکړل شوی صف د BST پروډرډ ټراورسل استازیتوب کولی شي

#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 پروډرډر ټراورسل استازیتوب کولی شي

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

د پیچلتیا تحلیل

د وخت پیچلتیا

O (N) ، ځکه چې موږ په ورکړل شوي آخذه صف کې ټول شاخصونه تیروو. پدې توګه د وخت پیچلتیا لاهم ده.

د ځای پیچلتیا

O (N) ، ځکه چې موږ یوه کښتۍ کارولې پدې توګه په بدترین حالت کې ، موږ کولی شو ټول نوډونه ذخیره کړو.