ตรวจสอบ Binary Tree มี Subtree ซ้ำขนาด 2 ขึ้นไปใน C++

ปัญหา

ตรวจสอบว่า Binary Tree มี Subtree ซ้ำกันขนาด ≥ 2 โหนดหรือไม่

ตัวอย่าง: Tree ที่มี Subtree โครงสร้างเหมือนกัน 2 ที่ (มีโหนด D, E ซ้ำ)

วิธีแก้: Tree Serialization + Hashing

1. Serialize subtree เริ่มจากโหนดใดโหนดหนึ่งเป็นสตริง (เช่น Preorder พร้อม marker สำหรับ NULL)
2. เก็บสตริงที่ serialize ได้ใน Hash Set
3. ถ้าเจอสตริงซ้ำ และความยาว > 3 (ไม่ใช่ leaf) → มี Subtree ซ้ำ

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

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

const char MARKER = '$';

struct Node {
    char data;
    Node *left, *right;
    Node(char val) : data(val), left(nullptr), right(nullptr) {}
};

unordered_set subtrees;

string serializeAndCheck(Node* root) {
    if (!root) return string(1, MARKER); // NULL → "$"
    
    string leftStr = serializeAndCheck(root->left);
    if (leftStr.empty()) return ""; // พบซ้ำใน subtree ซ้าย
    
    string rightStr = serializeAndCheck(root->right);
    if (rightStr.empty()) return ""; // พบซ้ำใน subtree ขวา
    
    // Serialize: root + left + right
    string serial = root->data + leftStr + rightStr;
    
    // ขนาด > 3 หมายถึงมีอย่างน้อย 2 โหนด (root + อย่างน้อย 1 child)
    if (serial.length() > 3 && subtrees.count(serial)) {
        return ""; // พบซ้ำ
    }
    
    subtrees.insert(serial);
    return serial;
}

bool hasDuplicateSubtree(Node* root) {
    subtrees.clear();
    string result = serializeAndCheck(root);
    return result.empty(); // empty = พบซ้ำ
}

int main() {
    //       A
    //      / \
    //     B   C
    //    / \   \
    //   D   E   B
    //            / \
    //           D   E
    
    Node* root = new Node('A');
    root->left = new Node('B');
    root->right = new Node('C');
    root->left->left = new Node('D');
    root->left->right = new Node('E');
    root->right->right = new Node('B');
    root->right->right->left = new Node('D');
    root->right->right->right = new Node('E');
    
    if (hasDuplicateSubtree(root))
        cout << "Has duplicate subtrees of size ≥ 2" << endl;
    else
        cout << "No duplicate subtrees of size ≥ 2" << endl;
    
    return 0;
}

ผลลัพธ์

Has duplicate subtrees of size ≥ 2

การ Serialize ตัวอย่าง

Subtree ที่ B (ซ้าย): "B D $ $ E $ $" (length 9)

Subtree ที่ B (ขวา): "B D $ $ E $ $" (length 9) → ซ้ำ! ✓

ความซับซ้อน

• เวลา: O(n²) worst case (string concatenation) สามารถปรับปรุงเป็น O(n) ด้วย hashing (Merkle tree)
• พื้นที่: O(n²) สำหรับเก็บสตริงทั้งหมด

การปรับปรุง: Merkle Hashing

แทน string ให้คำนวณ hash ของ subtree (เช่น SHA256 หรือ custom hash) เก็บ hash แทน string → O(n) เวลาและพื้นที่