ตรวจสอบ Isomorphic Tree ใน C++

โจทย์

กำหนด Binary Tree 2 ต้น ตรวจสอบว่า Isomorphic หรือไม่ (Tree หนึ่งได้มาจากอีกต้นด้วยการ Swap Left/Right Children ที่โหนดใดโหนดหนึ่งได้)

ตัวอย่าง

Tree 1:     1          Tree 2:     1
           / \                    / \
          2   3                  3   2
         / \   \                /   / \
        4   5   6              6   4   5
Isomorphic: True (Swap 2↔3 at root, then 4↔5 at node 2/3)

แนวคิด: Recursive

สองต้น Isomorphic ถ้า:

1. ทั้งคู่ NULL → True
2. หนึ่ง NULL → False
3. Root Value ต่างกัน → False
4. Recursive: (Left1 ~ Left2 AND Right1 ~ Right2) OR (Left1 ~ Right2 AND Right1 ~ Left2)

โค้ด C++

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

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool isIsomorphic(TreeNode* r1, TreeNode* r2) {
    // Both NULL
    if (!r1 && !r2) return true;
    // One NULL
    if (!r1 || !r2) return false;
    // Value mismatch
    if (r1->val != r2->val) return false;
    
    // Case 1: No flip at this level
    bool noFlip = isIsomorphic(r1->left, r2->left) && 
                  isIsomorphic(r1->right, r2->right);
    
    // Case 2: Flip at this level
    bool flip = isIsomorphic(r1->left, r2->right) && 
                isIsomorphic(r1->right, r2->left);
    
    return noFlip || flip;
}

TreeNode* createNode(int val) {
    return new TreeNode(val);
}

int main() {
    // Tree 1
    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);
    
    // Tree 2 (Isomorphic to Tree 1)
    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);
    
    cout << "Test 1: " << (isIsomorphic(r1, r2) ? "Isomorphic" : "Not Isomorphic") << endl;
    
    // Test 2: Different structure
    TreeNode* r3 = createNode(1);
    r3->left = createNode(2);
    r3->right = createNode(3);
    r3->left->left = createNode(4);
    
    TreeNode* r4 = createNode(1);
    r4->left = createNode(2);
    r4->right = createNode(3);
    r4->right->left = createNode(4); // Different structure
    
    cout << "Test 2: " << (isIsomorphic(r3, r4) ? "Isomorphic" : "Not Isomorphic") << endl;
    
    // Test 3: Different values
    TreeNode* r5 = createNode(1);
    r5->left = createNode(2);
    TreeNode* r6 = createNode(1);
    r6->left = createNode(3); // Different value
    cout << "Test 3: " << (isIsomorphic(r5, r6) ? "Isomorphic" : "Not Isomorphic") << endl;
    
    return 0;
}

Complexity

• Time: O(min(n₁, n₂)) - Visit nodes until mismatch
• Space: O(h) - Recursion stack (h = min height)
• Worst case: O(n) เมื่อ Tree เหมือนกันหรือ Isomorphic

Memoization Version (สำหรับ Subproblems ซ้ำ)

unordered_map<long long, bool> memo;

bool isIsomorphicMemo(TreeNode* r1, TreeNode* r2) {
    if (!r1 && !r2) return true;
    if (!r1 || !r2) return false;
    if (r1->val != r2->val) return false;
    
    long long key = ((long long)r1 << 32) | (long long)r2;
    if (memo.count(key)) return memo[key];
    
    bool noFlip = isIsomorphicMemo(r1->left, r2->left) && 
                  isIsomorphicMemo(r1->right, r2->right);
    bool flip = isIsomorphicMemo(r1->left, r2->right) && 
                isIsomorphicMemo(r1->right, r2->left);
    
    return memo[key] = (noFlip || flip);
}

ผลลัพธ์

Test 1: Isomorphic
Test 2: Not Isomorphic
Test 3: Not Isomorphic

สรูป

Isomorphic Tree = Trees ที่โครงสร้างเหมือนกันภายใต้การ Swap Left/Right Children ใดๆ Recursive Check ทั้ง Flip และ No-Flip ที่ทุกระดับ - คล้ายแต่ต่างจาก Symmetric Tree (Self-Mirror)