Ελέγξτε για πανομοιότυπα BST χωρίς να χτίσετε τα δέντρα


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Φανατικοί Fourkites
Δυαδικό δέντρο αναζήτησης Δυαδικό δέντρο Δέντρο

Δήλωση προβλήματος

«Ελέγξτε για πανομοιότυπα BSTs χωρίς να χτίζεις τα δέντρα »το πρόβλημα δηλώνει ότι σου δίνονται δύο συστοιχίες που αντιπροσωπεύουν μερικούς κόμβους. Δημιουργούμε λοιπόν 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

Κωδικός Java για Έλεγχος πανομοιότυπων 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) επιπλέον χώρος αλλά το πρόγραμμα στο σύνολό του έχει γραμμική πολυπλοκότητα χώρου.