C++ ব্যবহার করে সব ডুপ্লিকেট সাবট্রি বের করা

সমস্যা বিবরণ

ধরি একটি বাইনারি ট্রি আছে। আমাদের চেক করতে হবে ট্রিতে কিছু ডুপ্লিকেট সাবট্রি আছে কিনা। ধরি একটি বাইনারি ট্রি নিচের মতো:

এখানে আকার ২ এর দুটি একই সাবট্রি আছে। প্রতিটি সাবট্রিতে D, BD এবং BE-ও ডুপ্লিকেট সাবট্রি। আমরা ট্রি সিরিয়ালাইজেশন (tree serialization) এবং হ্যাশিং প্রসেস ব্যবহার করে এটি সমাধান করতে পারি। সাবট্রিগুলোর ইনঅর্ডার ট্রাভার্সাল হ্যাশ টেবিলে সংরক্ষণ করব। খালি নোডের জন্য ওপেনিং এবং ক্লোজিং প্যারেন্থেসিস ইনসার্ট করব।

উদাহরণ কোড

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

const char MARKER = '$';

struct Node {
public:
    char data;
    Node *left, *right;
};

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

unordered_set<string> subtrees;

string inorder(Node* node, unordered_map<string, int>& map) {
    if (!node)
        return "";
    string str = "(";
    str += inorder(node->left, map);
    str += to_string(node->data);
    str += inorder(node->right, map);
    str += ")";
    if (map[str] == 1)
        cout << node->data << " ";
    map[str]++;
    return str;
}

void duplicateSubtreeFind(Node *root) {
    unordered_map<string, int> map;
    inorder(root, map);
}

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');
    duplicateSubtreeFind(root);
}

আউটপুট

D E B