သစ်ပင်များကိုမဆောက်ဘဲတူညီသော BST များကိုစစ်ဆေးပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် ဝါသနာရှင်များ လေးကစ်
Binary Search Tree ဒွိသစ်ပင် သစ်ပင်

ပြProbleနာဖော်ပြချက်

"တူညီဘို့စစ်ဆေးပါ BSTသစ်ပင်များမဆောက်ရဟုဆိုသည် Array များ အချို့ node များကိုကိုယ်စားပြုသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် BST များကို arrays နှစ်ခုလုံးမှဖန်တီးပြီး၎င်း arrays မှဖန်တီးထားသော BST များသည်တူညီသည်မဟုတ်သည်ကိုပြောရန်လိုအပ်သည်။ ဒီမှာဖမ်းယူသည်မှာကျွန်ုပ်တို့သည်သစ်ပင်များကိုမဖန်တီးနိုင်ပါ။ သစ်ပင်တစ်ပင်တည်ဆောက်စရာမလိုဘဲသူတို့တူညီသည်မဟုတ်သည်ကိုတစ်နည်းနည်းဖြင့်စစ်ဆေးရန်လိုအပ်သည်။

နမူနာ

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

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

သစ်ပင်များကိုမဆောက်ဘဲတူညီသော BST များကိုစစ်ဆေးပါ

ရှင်းလင်းချက် - သစ်ပင်များတည်ဆောက်ခြင်းသူတို့နှစ်ခုစလုံးသည်အတူတူပင် ဖြစ်၍ တူညီသည်ဟုဆိုကြသည်။

သစ်ပင်များကိုမဆောက်လုပ်ဘဲတူညီသော BST များအတွက်စစ်ဆေးရန်နည်းလမ်း

ဤပြproblemနာကိုဖြေရှင်းရန်ကျွန်ုပ်တို့သည် recursion ကိုအသုံးပြုလိမ့်မည်။ ဤတွင်ကျွန်ုပ်တို့သည် binary search tree ၏အခြေခံဂုဏ်သတ္တိများကိုအသုံးပြုလိမ့်မည်။ ၄ င်းတို့မှာဘယ်ဘက် subtree ရှိ element အားလုံးသည် root ထက်သေးငယ်သည်။ root ၏ညာဘက်ရှိ element အားလုံးသည်၎င်းထက်ကြီးသည်။ ထို့ကြောင့်သစ်ပင်နှစ်ခုလုံး၏အမြစ်တူညီမှုရှိမရှိကိုစစ်ဆေးပြီးအမြစ်၏သားမြေးများသည်၎င်းအစဉ်လိုက်အစီအစဉ်တွင်ပါလာလိမ့်မည်။ ဒီတော့ root ကို Array နှစ်ခုစလုံးမှာ ၄ င်းရဲ့ကလေးများရှေ့မှာတွေ့ရမယ်။ ဤအခြေအနေသည်လက်ဝဲနှင့်လက်ယာခွဲများအတွက်လည်းကျေနပ်သင့်သည်။

ဤသည်ကိုပြန်လည်လုပ်ဆောင်နိုင်သည်။ ဘယ်ဘက် subtrees တူညီမလား၊ ညာဖက် subtree နှင့်အတူတူလားဆိုတာစစ်ဆေးဖို့သူ့ဟာသူခေါ်မယ့် function ကိုရေးမယ်။ ဤအခြေအနေများအားလုံးဖြတ်သန်းသွားသောအခါကျွန်ုပ်တို့သည် arrays နှစ်ခုလုံးမှကိုယ်စားပြုသော binary search tree သည်တူညီကြသည်။

ကုဒ်

သစ်ပင်များမဆောက်ဘဲစစ်ဆေးရန်အတွက် BST များအတွက် C ++ code

#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

သစ်ပင်များမဆောက်ဘဲ Check Boots များအတွက် Check for Java code

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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N) ဘာဖြစ်လို့လဲဆိုတော့ကျွန်တော်တို့ဟာ recursion လို့ခေါ်ပေမဲ့ arrays နှစ်ခုလုံးကိုဖြတ်သွားတယ်။ ဒါပေမယ့်လည်းကျွန်တော်တို့ဟာ indexing တစ်ခုအနေနဲ့ state တစ်ခုနဲ့အတူ recursion ကို run လိုက်တယ်၊ အဲဒါက linear အချိန်ရှုပ်ထွေးမှုကိုသေချာစေတယ်။

အာကာသရှုပ်ထွေးမှု

အို (N) ဘာလို့လဲဆိုတော့ကျနော်တို့ input ကိုသိမ်းဆည်းရန်ခင်းကျင်းကိုအသုံးပြုခဲ့သည်။ အဲ့တာအပြင်အခြားကိန်းဂဏန်းများကိုသာကျွန်ုပ်တို့အသုံးပြုခဲ့သည်။ ဒီတော့ algorithm ကိုယ်တိုင်ကပဲသုံးတယ် အို (၁) အပိုနေရာ ဒါပေမယ့်တစ်ခုလုံးအဖြစ်အစီအစဉ်ကို linear အာကာသရှုပ်ထွေးရှိပါတယ်။