BST의 요소를 나타내는 두 개의 배열이 있습니다. 해당 배열의 요소를 왼쪽에서 오른쪽으로 가져와 BST를 구성한 다음 두 배열에서 모두 가져와서 동일한 BST를 만듭니다. 둘 다 같은 모양인지 아닌지 확인해야 합니다. 그러나 제약은 우리가 BST를 만들 수 없다는 것입니다. 두 개의 배열이 {2, 4, 1, 3} 및 {2, 1, 4, 3}이라고 가정하면 이 두 시퀀스가 모두 동일한 BST를 형성할 수 있습니다.
접근 방식은 간단합니다. 우리가 알다시피 왼쪽 하위 트리의 요소는 루트보다 작고 오른쪽 하위 트리의 요소는 루트보다 큽니다. 이 두 목록은 각 요소 x에 대해 x의 왼쪽 및 오른쪽 하위 트리에 있는 요소가 두 배열 모두에서 그 뒤에 나타나는 경우 동일한 BST를 나타낼 수 있습니다. 왼쪽 및 오른쪽 하위 트리의 루트에 대해서도 마찬가지입니다. 다음으로 더 작은 요소와 더 큰 요소가 두 배열에서 동일한지 여부를 확인할 것입니다. 이 동일한 속성은 왼쪽 및 오른쪽 하위 트리에 대해 재귀적으로 확인됩니다.
예시
#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