Chúng tôi có hai mảng để đại diện cho các phần tử của BST. Nếu chúng ta lấy các phần tử từ mảng đó từ trái sang phải và tạo thành BST, thì bằng cách lấy từ cả hai mảng, chúng ta sẽ tạo nên BST giống nhau. Chúng tôi phải kiểm tra xem cả hai có đang hình thành giống nhau hay không. Nhưng hạn chế là chúng tôi không thể làm BST. Giả sử hai mảng là {2, 4, 1, 3} và {2, 1, 4, 3}, thì nếu chúng ta thấy, cả hai dãy này có thể tạo thành cùng một BST.
Cách tiếp cận rất đơn giản. Như chúng ta đã biết, các phần tử của cây con bên trái nhỏ hơn gốc và các phần tử của cây con bên phải lớn hơn gốc. Hai danh sách này có thể đại diện cho cùng một BST nếu đối với mỗi phần tử x, các phần tử trong cây con bên trái và bên phải của x xuất hiện sau nó trong cả hai mảng. Tương tự đối với các gốc của cây con trái và phải. Chúng tôi sẽ kiểm tra xem các phần tử nhỏ hơn và lớn hơn tiếp theo có giống nhau trong cả hai mảng hay không. Thuộc tính tương tự này được kiểm tra đệ quy cho các cây con bên trái và bên phải.
Ví dụ
#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";
}
} Đầu ra
Two BSTs are same