Kiểm tra cây Isomorphic trong C++

2 cây nhị phân isomorphic nếu có thể lật ngang (flip left/right) cây này thành cây kia.

Ví dụ

Output: Isomorphic

Tree-2 thu được bằng cách lật Tree-1.

Cách tiếp cận: Đệ quy

• Hàm isIsomorphicTree(r1, r2)
• Cả 2 NULL → True
• 1 NULL 1 không → False
• Data khác nhau → False
• Kiểm tra: (left1 với left2 AND right1 với right2) HOẶC (left1 với right2 AND right1 với left2)

Code C++

#include <bits/stdc++.h>
using namespace std;

struct treenode {
    int data;
    treenode* left;
    treenode* right;
};

struct treenode* createNode(int d) {
    struct treenode* root = new treenode;
    root->data = d; root->left = NULL; root->right = NULL;
    return root;
}

bool isIsomorphicTree(treenode* r1, treenode* r2) {
    if (!r1 && !r2) return true;
    if (!r1 || !r2) return false;
    return (r1->data == r2->data &&
        ((isIsomorphicTree(r1->left, r2->left) && isIsomorphicTree(r1->right, r2->right)) ||
         (isIsomorphicTree(r1->left, r2->right) && isIsomorphicTree(r1->right, r2->left))));
}

int main() {
    struct treenode* r1 = createNode(1);
    r1->left = createNode(2); r1->right = createNode(3);
    r1->left->left = createNode(4); r1->left->right = createNode(5);
    r1->right->left = createNode(6);
    r1->left->right->left = createNode(7); r1->left->right->right = createNode(8);

    struct treenode* r2 = createNode(1);
    r2->left = createNode(3); r2->right = createNode(2);
    r2->right->left = createNode(4); r2->right->right = createNode(5);
    r2->left->right = createNode(6);
    r2->right->right->left = createNode(8); r2->right->right->right = createNode(7);

    if (isIsomorphicTree(r1, r2)) cout << "Isomorphic" << endl;
    else cout << "Not an Isomorphic" << endl;
    return 0;
}

Kết quả

Isomorphic