C++에서 모든 중복 하위 트리 찾기

이진 트리가 있다고 가정합니다. 트리에 중복된 하위 트리가 있는지 여부를 찾아야 합니다. 아래와 같은 이진 트리가 있다고 가정합니다. -

크기가 2인 두 개의 동일한 하위 트리가 있습니다. 각 하위 트리에서 D, BD 및 BE 모두 중복 하위 트리입니다. 트리 직렬화 및 해싱 프로세스를 사용하여 이 문제를 해결할 수 있습니다. 해시 테이블에 하위 트리의 순회를 저장합니다. 빈 노드에 대해 여는 괄호와 닫는 괄호를 삽입합니다.

예시

#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