ตรวจสอบ Identical BSTs โดยไม่สร้าง Tree ใน C++

เรามี 2 Arrays แทน Elements ของ BST ถ้านำ Elements จาก Array ทั้งสองจากซ้ายไปขวาสร้าง BST จะได้ BST เดียวกัน ต้องตรวจสอบว่าเหมือนกันหรือไม่ โดยมีเงื่อนไขห้ามสร้าง BST จริง ตัวอย่าง Arrays {2, 4, 1, 3} และ {2, 1, 4, 3} สร้าง BST เหมือนกัน

แนวคิด: Elements ของ Left Subtree น้อยกว่า Root Right Subtree มากกว่า Root 2 Lists แทน BST เดียวกันได้ ถ้าสำหรับทุก Element x Elements ใน Left/Right Subtrees ของ x ปรากฏหลัง x ในทั้ง 2 Arrays ตรวจสอบ Next Smaller และ Greater Elements เหมือนกันในทั้ง 2 Arrays แบบ Recursive

ตัวอย่างโค้ด C++

#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) // parent is leaf in both
        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) && // right subtree
           isSameCheckHelper(tree1, tree2, n, j+1, k+1, min, tree1[j]); // 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