C++で二分木が対称（鏡像）かどうかを判定する方法

二分木が与えられ、それが自分自身の鏡像（対称）になっているかどうかを判定する問題を考えてみましょう。対称二分木とは、木全体が自身の鏡像と一致するような二分木のことです。

具体例

例1

入力：

出力：

True

説明：

与えられた二分木は自身の鏡像と一致しているため、出力は True になります。

例2

入力：

出力：

False

説明：

与えられた二分木は鏡像になっていないため、対称な木ではありません。

この問題の解き方

対称な二分木とは、自分自身の鏡像となっている木のことです。つまり、木の左側の部分木と右側の部分木が互いに鏡像の関係にあるかどうかを確認すればよいことになります。

具体的には、ブール型の関数で最初に左のノードと右のノードをチェックします。両方のノードが空（NULL）であれば True を返します。それ以外の場合は、左右の子が存在するときに値が一致していなければならず、これが成り立つときのみ木は対称であると判断できます。

• ルートとその子を含む二分木を用意します。
• ブール型のヘルパー関数 helper(node* root1, node* root2) は、同じ木の2つのノードを受け取り、左の子と右の子が一致しているかどうかの判定を補助します。
• 木が空または NULL の場合は True を返します。
• 再帰的に、左側のノードと右側のノードが等しいかどうかを調べます。このとき、片方の左の子ともう片方の右の子を比較するのがポイントです。
• 上記のいずれの条件も満たさない場合は False を返します。

C++での実装例

#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

説明：

このコードでは、ルートの左右に配置された子の値の組み合わせ（5 と 7 の位置）が鏡像になっていないため、与えられた木は対称ではないと判断され、出力は False になります。