หาต้นไม้ย่อยซ้ำ (Duplicate Subtrees) ทั้งหมดใน C++

ข้อความโจทย์

พิจารณาว่าเรามีต้นไม้แบบทวิภาค (Binary Tree) เราต้องหาว่ามีต้นไม้ย่อยซ้ำ (Duplicate Subtrees) ในต้นไม้หรือไม่ สมมติเรามีต้นไม้แบบทวิภาคดังนี้ -

มีต้นไม้ย่อยเหมือนกันสองต้นขนาด 2 ในแต่ละต้นไม้ย่อย D, BD และ BE ก็เป็นต้นไม้ย่อยซ้ำเช่นกัน เราสามารถแก้ปัญหานี้ได้โดยใช้การทำซีเรียลไลซ์ต้นไม้ (Tree Serialization) และกระบวนการแฮชชิง (Hashing) เราจะเก็บการท่องอินออร์เดอร์ (Inorder Traversal) ของต้นไม้ย่อยในตารางแฮช เราจะใส่วงเล็บเปิดและปิดสำหรับโหนดว่าง

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

#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