Semak BST yang sama tanpa membina pokok di C ++

Cplusplus Server-Side-Programming Programming

Kami mempunyai dua baris untuk mewakili elemen BST. Jika kita mengambil elemen dari array itu dari kiri ke kanan, dan membentuk BST, kemudian dengan mengambil dari kedua-dua array, kita akan membuat BST yang sama. Kita perlu menyemak sama ada kedua-duanya membentuk sama atau tidak. Tetapi kekangannya ialah kita tidak boleh membuat BST. Katakan dua baris adalah {2, 4, 1, 3}, dan {2, 1, 4, 3}, maka jika kita lihat, kedua-dua urutan ini boleh membentuk BST yang sama.

Pendekatannya mudah. Seperti yang kita tahu, elemen subtree kiri lebih kecil daripada akar dan elemen subtree kanan lebih besar daripada akar. Kedua-dua senarai ini boleh mewakili BST yang sama jika bagi setiap elemen x, elemen-elemen dalam subtrees kiri dan kanan x muncul selepas ia dalam kedua-dua tatasusunan. Begitu juga dengan akar pokok kiri dan kanan. Kami akan menyemak sama ada unsur yang lebih kecil dan lebih besar seterusnya sama dalam kedua-dua tatasusunan. Harta yang sama ini diperiksa secara rekursif untuk subtrees kiri dan kanan.

Contoh

 #include <iostream>
using namespace std;
bool isSameCheckHelper(int tree1[], int tree2[], int n, int i1, int i2, int min, int max) {
   int j, k;
   for (j = i1; j < n; j++)
      if (tree1[j] > min && tree1[j] < max)
   break;
   for (k = i2; k < n; k++)
      if (tree2[k] > min && tree2[k] < max)
   break;
   if (j==n && k==n) //If the parent element is leaf in both arrays
      return true;
   if (((j==n)^(k==n)) || tree1[j]!=tree2[k])
      return false;
   return isSameCheckHelper(tree1, tree2, n, j+1, k+1, tree1[j], max) &&
   // for Right Subtree
   isSameCheckHelper(tree1, tree2, n, j+1, k+1, min, tree1[j]); // for Left Subtree
}
bool areBSTSame(int first[], int second[], int n) {
   return isSameCheckHelper(first, second, n, 0, 0, INT_MIN, INT_MAX);
}
int main() {
   int first[] = {8, 3, 6, 1, 4, 7, 10, 14, 13};
   int second[] = {8, 10, 14, 3, 6, 4, 1, 7, 13};
   int n=sizeof(first)/sizeof(first[0]);
   if(areBSTSame(first, second, n)) {
      cout << "Two BSTs are same";
   } else {
      cout << "Two BSTs are not same";
   }
} 

Pengeluaran

Two BSTs are same
2020-02-08 13:45
drifterdenim
Joseph Harris