C++の対称ツリー

二分木があり、それがそれ自体の対称性を構築するかどうかをチェックすることがタスクであると仮定しましょう。対称二分木はそれ自体の鏡像を構築します。

例

入力-1：

出力：

True

説明：

与えられた二分木はそれ自体の鏡像を構築するので、出力はTrueです。

入力-2：

出力：

False

説明：

与えられた二分木はそれ自体の鏡像を作らないので、対称的ではありません。

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

対称二分木は、それ自体の鏡像であるツリーです。つまり、ツリーの左右のノードが同じであるかどうかを確認する必要があります。

ブール関数は、最初に左側のノードと右側のノードをチェックします。ノードが空またはNULLの場合、Trueを返します。それ以外の場合は、左または右の子があるかどうかを確認します。対称ツリーになるように、同じである必要があります。

• ルートとその子を含む二分木を取ります。
• ブールヘルパー関数helper（node * root1、node * root2）は、同じツリーの2つのルートを取り、左の子と右の子が同じかどうかを確認するのに役立ちます。
• ツリーが空またはNULLの場合、Trueを返します。
• ツリーの左側のノードと右側のノードが等しいかどうかを再帰的に確認します。
• 上記のすべての条件が満たされない場合はFalseを返します。

例

#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 helper(struct treenode * root1, struct treenode * root2) {
   if (root1 == NULL and root2 == NULL)
      return true;
   if (root1 and root2 and root1 -> data == root2 -> data)
      return (helper(root1 -> left, root2 -> right) and helper(root1 -> right, root2 -> left));
   return false;
}
bool isSymmetry(struct treenode * root) {
   return helper(root, root);
}
int main() {
   struct treenode * root = NULL;
   root = createNode(4);
   root -> left = createNode(2);
   root -> right = createNode(2);
   root -> left -> right = createNode(7);
   root -> left -> left = createNode(5);
   root -> right -> left = createNode(5);
   root -> right -> right = createNode(7);
   if (isSymmetry(root)) {
      cout << "True" << endl;
   } else {
      cout << "False" << endl;
   }
   return 0;
}

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

出力

False

説明：

指定されたツリーは対称ではないため、出力はFalseとして取得されます。