Модыг барихгүйгээр ижил төстэй БСТ байгаа эсэхийг шалгана уу


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Фанатикууд Фуркайт
Хоёртын хайлтын мод Хоёртын мод Мод

Асуудлын мэдэгдэл

“Ижил төстэй эсэхийг шалгана уу BSTмодыг барихгүйгээр с ”гэсэн гарчигтай асуудалд танд хоёрыг өгсөн гэж заасан байдаг массивууд зарим зангилааг төлөөлдөг. Тиймээс бид массивын аль алинаас нь BST үүсгэж байгаа тул эдгээр массиваас үүссэн BST нь ижил байх уу үгүй ​​юу гэдгийг хэлэх хэрэгтэй байна уу? Бид модоо бүтээж чадахгүй (өөрөөр хэлбэл бид модоо барьж, дараа нь харьцуулж чадахгүй). Мод барихгүйгээр бид адилхан байгаа эсэхийг нь ямар нэгэн байдлаар шалгах хэрэгтэй.

Жишээ нь

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

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

Модыг барихгүйгээр ижил төстэй БСТ байгаа эсэхийг шалгана уу

Тайлбар: Мод барих талаар bтэдгээрийн зарим нь адилхан харагдаж байгаа тул ижил төстэй гэж хэлдэг.

Модыг барихгүйгээр ижил BST-ийг шалгах арга

Энэ асуудлыг шийдэхийн тулд бид рекурсийг ашиглах болно. Энд бид хоёртын хайлтын модны зарим үндсэн шинж чанаруудыг ашиглах бөгөөд зүүн дэд модны бүх элементүүд үндэснээс бага байна. Язгуурын баруун талд байгаа бүх элементүүд үүнээс том байна. Тиймээс, хоёр модны үндэс ижил эсэхийг, мөн түүний үр хүүхдүүд массивын дарааллаар араас нь ирэх эсэхийг шалгана. Тиймээс root нь массивын аль алинд нь хүүхдүүдийнхээ өмнө байдаг. Энэ нөхцөл байдал нь зүүн, баруун дэд модны хувьд ч гэсэн хангагдсан байх ёстой.

Үүнийг рекурсив байдлаар хийж болно. Тиймээс бид зүүн дэд моднууд ижил, баруун дэд модонд адилхан байгаа эсэхийг шалгахын тулд өөрсдийгөө дуудах функц бичдэг. Эдгээр бүх нөхцлүүд өнгөрөхөд бид массивын хоёуланг нь төлөөлсөн хоёртын хайлтын мод ижил байна гэж хэлье.

код

Модыг барихгүйгээр ижил төстэй BST-ийг шалгах 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

Модыг барихгүйгээр ижил төстэй BST-ийг шалгах 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 (N) Учир нь бид рекурс гэж нэрлэсэн ч гэсэн массивыг хоёуланг нь туулсан. Гэхдээ дараа нь бид массивын дагуу рекурсийг нэг төлөв байдлаар индекс болгон ажиллуулж шугаман хугацааны нарийн төвөгтэй байдлыг хангасан болно.

Сансрын нарийн төвөгтэй байдал

O (N) Учир нь бид оролтыг хадгалахын тулд массив ашигласан. Үүнээс гадна бид тогтмол тооны хувьсагчийг ашигласан болно. Тиймээс алгоритм нь зөвхөн ашигладаг O (1) нэмэлт зай Гэхдээ хөтөлбөр нь бүхэлдээ орон зайн шугаман нарийн төвөгтэй байдаг.