バイナリツリーに、C++でサイズ2以上の重複するサブツリーが含まれていないかどうかを確認します

二分木があると考えてください。ツリーにサイズ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