БСТ-ҳои шабеҳро бидуни сохтани дарахтон санҷед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Фараж Фуркайтҳо
Дарахти ҷустуҷӯи бинарӣ Дарахти дуӣ Дарахт

Изҳороти мушкилот

“Якхеларо санҷед БАСҳо бе сохтани дарахтон »мушкилот изҳор медорад, ки ба шумо дуто медиҳанд массиви ки баъзе гиреҳҳоро намояндагӣ мекунанд. Пас, мо ҳарду массивро БСТ месозем, акнун мо бояд бигӯем, ки БСТ-ҳои аз ин массивҳо сохташуда якхелаанд ё не? Дар ин ҷо сайд кардан мумкин аст, ки мо дарахтонро эҷод карда наметавонем (яъне дарахтонро сохта наметавонем ва баъд онҳоро муқоиса карда наметавонем). Мо бояд бо як навъ тафтиш кунем, ки онҳо якхелаанд ё не, бе бунёди дарахт.

мисол

Arr1[] = {2, 1, 4, 3, 5}

Arr2[] = {2, 4, 5, 3, 1}
Yes

БСТ-ҳои шабеҳро бидуни сохтани дарахтон санҷед

Шарҳ: Дар бораи бунёди дарахтон ббаъзеи онҳо якхела ба назар мерасанд ва ҳамин тавр гуфта мешавад, ки онҳо якхелаанд.

Усули санҷиши якхелаи БСТ бидуни сохтани дарахтон

Барои ҳалли ин масъала мо рекурсияро истифода мебарем. Дар ин ҷо мо баъзе хосиятҳои дарахтҳои ҷустуҷӯии дутарафаро истифода хоҳем кард, ки ҳамаи элементҳои дар зер дарахти чап буда аз реша хурдтаранд. Дар ҳоле ки ҳамаи унсурҳои рости реша аз он бузургтаранд. Ҳамин тавр, мо месанҷем, ки решаи ҳарду дарахт як аст ва фарзандони реша пас аз он дар пайдарпаии массив меоянд. Пас, реша дар назди фарзандони худ дар ҳарду массив мавҷуд аст. Ин шарт бояд барои дарахтони чап ва рост низ қонеъ карда шавад.

Ин метавонад рекурсивӣ бошад. Ҳамин тавр, мо вазифаеро менависем, ки ба худ занг мезанад, то санҷад, ки зерсохтори чап якхела аст ва ҳамон чизе ба зери дарахти рост ҳам дахл дорад. Вақте ки ҳамаи ин шартҳо мегузаранд, мо мегӯем, ки дарахтҳои ҷустуҷӯии дуӣ, ки ҳарду массив доранд, якхелаанд.

рамз

Рамзи C ++ барои Санҷиши БСТ-ҳои шабеҳ бидуни сохтани дарахтон

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

// this function checks if the BSTs are identical or not
// Here the i1 & i2 represent the indices in the arrays arr1 and arr2
// The minimum & maximum are used for defining the bounds of left and right subtree
bool areBSTsIdentical(int arr1[], int arr2[], int n, int i1, int i2, int minimum, int maximum)
{
    // find the first element in a which lies between minimum and maximum value
    // here we find the node which becomes the root of either the left or right subtree
    // depending upon the value of minimum and maximum
  int j, k;
  for (j = i1; j < n; j++)
  if (arr1[j] > minimum && arr1[j] < maximum)
    break;
  for (k = i2; k < n; k++)
    if (arr2[k] > minimum && arr2[k] < maximum)
      break;


    // base case
    // current node is a leaf in both the trees
    if (j==n && k==n)
        return true;

    bool oneLeafOtherNonLeaf = ((j==n)^(k==n));
    // current node is leaf in one of the trees but not in other.
    // the first number which satisfy the given constraint must be same in both the arrays
    // because they serve as root of the subtrees
    if (oneLeafOtherNonLeaf || arr1[j]!=arr2[k])
        return false;

    // recursively solve for left and right subtree
    return areBSTsIdentical(arr1, arr2, n, j+1, k+1, arr1[j], maximum) && areBSTsIdentical(arr1, arr2, n, j+1, k+1, minimum, arr1[j]);
}

int main()
{
    int arr1[] = {2, 1, 4, 3, 5};
    int arr2[] = {2, 4, 5, 3, 1};
  int n=sizeof(arr1)/sizeof(arr1[0]);
  bool answer = areBSTsIdentical(arr1, arr2, n, 0, 0, INT_MIN, INT_MAX);
  cout<<(answer ? "YES" : "NO");
  return 0;
}
YES

Рамзи Java барои Санҷиши БСТ-ҳои шабеҳ бидуни сохтани дарахтон

class Main
{ 

  // this function checks if the BSTs are identical or not
  // Here the i1 & i2 represent the indices in the arrays arr1 and arr2
  // The minimum & maximum are used for defining the bounds of left and right subtree
  static boolean areBSTsIdentical(int arr1[], int arr2[], int n, int i1, int i2, int minimum, int maximum) 
  { 
    // find the first element in a which lies between minimum and maximum value
      // here we find the node which becomes the root of either the left or right subtree
      // depending upon the value of minimum and maximum
    int j, k;
    for (j = i1; j < n; j++)
    if (arr1[j] > minimum && arr1[j] < maximum)
      break;
    for (k = i2; k < n; k++)
      if (arr2[k] > minimum && arr2[k] < maximum)
        break;
  
  
      // base case
      // current node is a leaf in both the trees
      if (j==n && k==n)
          return true;
  
      boolean oneLeafOtherNonLeaf = ((j==n)^(k==n));
      // current node is leaf in one of the trees but not in other.
      // the first number which satisfy the given constraint must be same in both the arrays
      // because they serve as root of the subtrees
      if (oneLeafOtherNonLeaf || arr1[j]!=arr2[k])
          return false;
  
      // recursively solve for left and right subtree
      return areBSTsIdentical(arr1, arr2, n, j+1, k+1, arr1[j], maximum) && areBSTsIdentical(arr1, arr2, n, j+1, k+1, minimum, arr1[j]);
  } 
  
  public static void main(String[] args) 
  {
    int arr1[] = {2, 1, 4, 3, 5};
    	        int arr2[] = {2, 4, 5, 3, 1};
    int n=arr1.length; 
    boolean answer = areBSTsIdentical(arr1, arr2, n, 0, 0, Integer.MIN_VALUE, Integer.MAX_VALUE);
    System.out.print(answer ? "YES" : "NO");
  } 
}
YES

Таҳлили мураккабӣ

Мураккабии вақт

О (Н) зеро мо танҳо ҳарду массивро тай кардем, гарчанде ки мо рекурсия номида будем. Аммо баъдан мо низ рекурсияро дар массив бо як ҳолат ҳамчун индекс иҷро кардем, ки мураккабии хаттии вақтро таъмин кард.

Мураккабии фазо

О (Н) зеро мо барои нигоҳ доштани вуруд массивро истифода кардем. Ба ғайр аз ин, мо танҳо баъзе миқдори доимии тағирёбандаҳоро истифода кардем. Пас худи алгоритм танҳо истифода мебарад O (1) фазои иловагӣ аммо барнома дар маҷмӯъ мураккабии хаттии кайҳонӣ дорад.