Kiểm tra cây nhị phân có cây con trùng lặp size ≥ 2 C++

Kiểm tra cây nhị phân có cây con trùng lặp (cùng cấu trúc và giá trị) kích thước ≥ 2 không.

Giải thuật (Serialization + Hashing)

1. Serialize cây con thành string (preorder với marker '$' cho NULL)
2. Lưu các string serialize vào unordered_set
3. Nếu gặp string đã tồn tại và độ dài > 3 (không phải lá) → có trùng lặp

Ví dụ minh họa

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

const char MARKER = '$';

struct Node {
    char key;
    Node *left, *right;
};

Node* getNode(char key) {
    Node* n = new Node;
    n->key = key; n->left = n->right = NULL;
    return n;
}

unordered_set<string> subtrees;

string dupSubtreeUtil(Node* root) {
    if (!root) return string(1, MARKER);
    
    string lStr = dupSubtreeUtil(root->left);
    if (lStr.empty()) return "";
    
    string rStr = dupSubtreeUtil(root->right);
    if (rStr.empty()) return "";
    
    string res = string(1, root->key) + lStr + rStr;
    
    if (res.length() > 3 && subtrees.count(res))
        return ""; // tim thay trung lap
    
    subtrees.insert(res);
    return res;
}

int main() {
    Node* root = getNode('A');
    root->left = getNode('B'); root->right = getNode('C');
    root->left->left = getNode('D'); root->left->right = getNode('E');
    root->right->right = getNode('B');
    root->right->right->left = getNode('D');
    root->right->right->right = getNode('E');
    
    string str = dupSubtreeUtil(root);
    cout << (str.empty() ? "Co cay con trung lap size >= 2" : "Khong co cay con trung lap");
}

Kết quả

Co cay con trung lap size >= 2