Kiểm tra hai BST giống nhau không cần xây cây trong C++

Cho hai mảng biểu diễn thứ tự chèn vào BST. Kiểm tra xem hai mảng có tạo ra cùng một BST hay không, mà không được xây dựng cây thực tế. Ví dụ {2, 4, 1, 3} và {2, 1, 4, 3} tạo ra BST giống nhau.

Ý tưởng: với mỗi nút x, các phần tử cây con trái/phải phải xuất hiện sau x trong cả hai mảng. Kiểm tra đệ quy: tìm phần tử tiếp theo trong khoảng (min, max) cho cả hai mảng, so sánh giá trị, rồi đệ quy cho cây con trái (min, x) và phải (x, max).

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)
        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) &&
           isSameCheckHelper(tree1, tree2, n, j+1, k+1, min, tree1[j]);
}

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";
    }
}

Kết quả

Two BSTs are same