เรามีสองอาร์เรย์เพื่อแสดงองค์ประกอบของ BST หากเรานำองค์ประกอบจากอาร์เรย์นั้นจากซ้ายไปขวา และสร้าง BST จากนั้นเราจะสร้าง BST เดียวกันโดยการดึงจากทั้งสองอาร์เรย์ เราต้องตรวจสอบว่าทั้งสองมีรูปร่างเหมือนกันหรือไม่ แต่ข้อจำกัดคือเราไม่สามารถสร้าง BST ได้ สมมติว่าสองอาร์เรย์คือ {2, 4, 1, 3} และ {2, 1, 4, 3} ถ้าเราเห็น ทั้งสองลำดับเหล่านี้สามารถสร้าง BST เดียวกันได้
วิธีการนั้นง่าย ดังที่เราทราบ องค์ประกอบของทรีย่อยทางซ้ายมีขนาดเล็กกว่ารูท และองค์ประกอบของทรีย่อยทางขวานั้นมากกว่ารูท สองรายการนี้สามารถแสดง BST เดียวกันได้หากองค์ประกอบ x แต่ละองค์ประกอบในทรีย่อยด้านซ้ายและด้านขวาของ x ปรากฏขึ้นหลังจากในอาร์เรย์ทั้งสอง เช่นเดียวกับรากของทรีย่อยซ้ายและขวา เราจะตรวจสอบว่าองค์ประกอบที่เล็กกว่าและมากกว่าถัดไปนั้นเหมือนกันในทั้งสองอาร์เรย์หรือไม่ คุณสมบัติเดียวกันนี้มีการตรวจสอบซ้ำสำหรับทรีย่อยซ้ายและขวา
ตัวอย่าง
#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";
}
} ผลลัพธ์
Two BSTs are same
