C++ में बाइनरी ट्री में आकार 2 या अधिक के डुप्लिकेट सबट्री हैं या नहीं जांचें

समस्या विवरण

बाइनरी ट्री में आकार 2 या अधिक के डुप्लिकेट सबट्री हैं या नहीं जांचें।

हल: ट्री सीरियलाइजेशन + हैशिंग

1. प्रत्येक सबट्री को स्ट्रिंग के रूप में सीरियलाइज़ करें (नल के लिए '$' मार्कर)
2. सीरियलाइज्ड स्ट्रिंग्स को हैश सेट में स्टोर करें
3. यदि कोई नॉन-लीफ सबट्री पहले से सेट में है → डुप्लिकेट मिल गया

उदाहरण कोड

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

const char MARKER = '$';

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

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

unordered_set subtrees;

string duplicateSubtreeFind(Node* root) {
    string res = "";
    if (root == NULL) return res + MARKER;
    
    string lStr = duplicateSubtreeFind(root->left);
    if (lStr == res) return res;
    
    string rStr = duplicateSubtreeFind(root->right);
    if (rStr == res) return res;
    
    res = res + root->key + lStr + rStr;
    
    if (res.length() > 3 && subtrees.find(res) != subtrees.end())
        return "";
    
    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->right = getNode('E');
    root->right->right->left = getNode('D');
    
    string str = duplicateSubtreeFind(root);
    if (str == "")
        cout << "It has duplicate subtrees of size more than 1";
    else
        cout << "It has no duplicate subtrees of size more than 1";
    return 0;
}

आउटपुट

It has duplicate subtrees of size more than 1