بدون ساختن درختان BST های یکسان را بررسی کنید


سطح دشواری متوسط
اغلب در متعصبان فورکایت
درخت جستجوی دودویی درخت باینری درخت

بیان مسأله

"برای یکسان بودن را بررسی کنید BSTبدون ساختن درختان »مشکل بیان می کند که دو مورد به شما داده می شود آرایه ها که نشان دهنده برخی از گره ها است. بنابراین ما از هر دو آرایه BST ایجاد می کنیم اکنون باید بگوییم BST ایجاد شده از این آرایه ها یکسان خواهد بود یا خیر؟ در اینجا صید ما این است که ما نمی توانیم درختان را ایجاد کنیم (یعنی نمی توانیم درختان را بسازیم و سپس آنها را مقایسه کنیم). ما باید بدون ساختن درخت به نوعی بررسی کنیم که آیا یکسان هستند یا نه.

مثال

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

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

بدون ساختن درختان BST های یکسان را بررسی کنید

توضیح: در مورد ساختن درختان بهر دو از آنها یکسان به نظر می رسند و بنابراین گفته می شود که یکسان هستند.

رویکرد بررسی BST های یکسان بدون ساختن درختان

ما برای حل این مشکل از بازگشت استفاده خواهیم کرد. در اینجا ما از برخی از خصوصیات اصلی درختان جستجوی دودویی استفاده خواهیم کرد که عبارتند از اینکه همه عناصر موجود در زیر درخت سمت چپ کوچکتر از ریشه هستند. در حالی که تمام عناصر سمت راست ریشه بزرگتر از آن هستند. بنابراین ، بررسی خواهیم کرد که آیا ریشه هر دو درخت یکسان است یا خیر ، و فرزندان ریشه نیز به ترتیب دنباله می آیند. بنابراین ریشه قبل از فرزندان در هر دو آرایه وجود دارد. این شرایط باید برای زیرشاخه چپ و راست نیز رعایت شود.

این کار را می توان به صورت بازگشتی انجام داد. بنابراین ما تابعی را می نویسیم که خود را فراخوانی می کند تا بررسی کند که درخت های فرعی سمت چپ یکسان هستند یا خیر ، و همین امر برای درخت فرعی سمت راست نیز صادق است. وقتی همه این شرایط گذشت ، می گوییم درختان جستجوی باینری که توسط هر دو آرایه نمایش داده می شوند یکسان هستند.

رمز

کد C ++ برای بررسی BST های یکسان بدون ساختن درختان

#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 های یکسان بدون ساختن درختان

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) فضای اضافی اما این برنامه به عنوان یک کل دارای پیچیدگی فضای خطی است.