C++에서 이진 트리에 크기가 2 이상인 중복 하위 트리가 포함되어 있는지 확인하십시오.

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

크기가 2인 두 개의 동일한 하위 트리가 있습니다. 트리 직렬화와 해싱 프로세스를 사용하여 이 문제를 해결할 수 있습니다. 아이디어는 하위 트리를 문자열로 직렬화하여 해시 테이블에 저장하는 것입니다. 리프가 아니고 이미 해시 테이블에 존재하는 직렬화된 트리를 찾으면 true를 반환합니다.

예시

#include <iostream>
#include <unordered_set>
using namespace std;
const char MARKER = '$';
struct Node {
   public:
   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<string> subtrees;
string duplicateSubtreeFind(Node *root) {
   string res = "";
   if (root == NULL) // If the current node is NULL, return $
      return res + MARKER;
   string l_Str = duplicateSubtreeFind(root->left);
   if (l_Str.compare(res) == 0)
      return res;
   string r_Str = duplicateSubtreeFind(root->right);
   if (r_Str.compare(res) == 0)
      return res;
   res = res + root->key + l_Str + r_Str;
   if (res.length() > 3 && subtrees.find(res) != subtrees.end()) //if subtree is present, then return blank string 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.compare("") == 0)
      cout << "It has dublicate subtrees of size more than 1";
   else
      cout << "It has no dublicate subtrees of size more than 1" ;
}

출력

It has dublicate subtrees of size more than 1