ツリーがC++で同形であるかどうかを確認します

二分木では、各ノードに2つの子、つまり左の子と右の子が含まれます。 2つの二分木があり、タスクは、ツリーの1つが、別のツリーを左にひっくり返すことによって取得できるかどうかを確認することであると仮定します。

左側にある他のツリーを反転して取得できる場合、ツリーは同型です。

例

入力-1

出力： 同形

説明： 与えられたTree-2は、左側のTree-1を反転することで取得できるため、Treeは同型です。

この問題を解決するためのアプローチ

この特定の問題を解決するための再帰的なアプローチは、ブール関数が両方のツリーのルートノードをチェックすることです。両方のツリーのルートが空またはNULLの場合は、Trueを返し、両方のルートに同じデータがあるかどうかを再帰的にチェックします。次に、ツリーの左右のノードを再帰的にチェックします。

• 2つの二分木のノードを作成します。
• ブール関数isIsomorphicTree（node * r1、node * r2）は、2つのツリーのルートを取得し、ツリーが同型であるかどうかを返します。
• 最初に、ツリーが空であるか、ノードが含まれていない場合は、Trueを返します。
• ルート化されたサブツリーが反転されておらず、両方が反転されている場合は、Trueを返します。

例

#include<bits/stdc++.h>
using namespace std;
struct treenode {
   int data;
   treenode * left;
   treenode * right;
};
struct treenode * createNode(int d) {
   struct treenode * root = new treenode;
   root -> data = d;
   root -> left = NULL;
   root -> right = NULL;
   return root;
}
bool isIsomorphicTree(treenode * r1, treenode * r2) {
   if (r1 == NULL and r2 == NULL) {
      return true;
   }
   if (r1 == NULL or r2 == NULL) {
      return false;
   }
   return (r1 -> data == r2 -> data &amp;&amp; ((isIsomorphicTree(r1 -> left, r2 -> right) &amp;&amp;       isIsomorphicTree(r1 -> right, r2 -> left)) || (isIsomorphicTree(r1 -> left, r2 -> left) &amp;&amp; isIsomorphicTree(r1 -> right, r2 -> right))));
}
int main() {
   struct treenode * r1 = createNode(1);
   r1 -> left = createNode(2);
   r1 -> right = createNode(3);
   r1 -> left -> left = createNode(4);
   r1 -> left -> right = createNode(5);
   r1 -> right -> left = createNode(6);
   r1 -> left -> right -> left = createNode(7);
   r1 -> left -> right -> right = createNode(8);
   struct treenode * r2 = createNode(1);
   r2 -> left = createNode(3);
   r2 -> right = createNode(2);
   r2 -> right -> left = createNode(4);
   r2 -> right -> right = createNode(5);
   r2 -> left -> right = createNode(6);
   r2 -> right -> right -> left = createNode(8);
   r2 -> right -> right -> right = createNode(7);
   if (isIsomorphicTree(r1, r2)) {
      cout << "Isomorphic" << endl;
   } else {
      cout << "Not an Isomorphic" << endl;
   }
   return 0;
}

上記のコードを実行すると、次のように出力が生成されます

出力

Isomorphic

説明： 与えられた木は、もう一方の木を左側にひっくり返すことで取得できるため、同型です。