C++で二分木のフリップ等価性を判定する方法【再帰による実装例つき】

問題の概要

2つの二分木が与えられ、一方の木をもう一方の木へ変換できるかどうかを判定する問題を考えてみましょう。

ここでいうフリップ（反転）操作とは、任意のノードを1つ選び、そのノードの左側の子部分木と右側の子部分木を入れ替えることです。二分木 X にフリップ操作を何度か適用して二分木 Y と同じ形にできるとき、X と Y はフリップ等価であると言います。

本記事では、ルートノード root1 と root2 として与えられる2つの二分木がフリップ等価かどうかを判定するメソッドを、C++で実装していきます。

上図のような2つの木の場合、値が 1、3、5 のノードでフリップ操作を行えば、一方の木をもう一方の木に一致させられるため、結果は true（真）となります。

解法のアプローチ

この問題は再帰処理を使うとすっきり解けます。ポイントは、各ノードの段階で「子をそのまま比較すればよいのか」「左右を入れ替えて比較すべきなのか」を判断することです。手順は以下の通りです。

1. 2つの木（ノード）t1 と t2 を引数に取る再帰関数 solve() を定義します。
2. t1 と t2 がどちらも null の場合は true を返します（両方とも空なので等価です）。
3. 片方だけが null の場合は false を返します（構造が異なるためです）。
4. 両方のノードが存在する場合は、まずノードの値を比較し、値が異なれば false を返します。
5. 値が同じ場合は、さらに次のように場合分けします。
   • そのまま比較できるケース：（t1 と t2 の両方に左の子がない）または（両方に左の子があり、その値が等しい）場合 → solve(t1の左, t2の左) と solve(t1の右, t2の右) の結果を返します。
   • 入れ替えて比較するケース：上記以外の場合 → 左右を交差させて solve(t1の左, t2の右) と solve(t1の右, t2の左) の結果を返します。

すべての再帰呼び出しが true を返せば、2つの木はフリップ等価であると判定できます。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = NULL;
        right = NULL;
    }
};
// 幅優先順で値を挿入し、木を構築する補助関数
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        }else{
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class Solution {
    public:
    bool flipEquiv(TreeNode* root1, TreeNode* root2) {
        // 両方とも空なら等価
        if(!root1 && !root2)return true;
        // 片方だけ空なら非等価
        else if(!root1 || !root2)return false;
        // ノードの値が異なれば非等価
        else if(root1->val != root2->val) return false;
        else if((!root1->left && !root2->left) || (root1->left && root2->left && root1->left->val == root2->left->val)){
            // 左右をそのまま対応付けて比較
            return flipEquiv(root1->left, root2->left) && flipEquiv(root1->right, root2->right);
        }else{
            // 左右を入れ替えて比較
            return flipEquiv(root1->left, root2->right) && flipEquiv(root1->right, root2->left);
        }
    }
};
main(){
    vector<int> v = {1,2,3,4,5,6,NULL,NULL,NULL,7,8};
    TreeNode *r1 = make_tree(v);
    vector<int> v1 = {1,3,2,NULL,6,4,5,NULL,NULL,NULL,NULL,NULL,NULL,8,7};
    TreeNode *r2 = make_tree(v1); // 2本目の木は v1 から構築する
    Solution ob;
    cout << (ob.flipEquiv(r1, r2));
}

入力

[1,2,3,4,5,6,null,null,null,7,8]
[1,3,2,null,6,4,5,null,null,null,null,null,null,8,7]

出力

1

出力が 1（true）となり、2つの木がフリップ等価であることが確認できました。

計算量について

このアルゴリズムでは各ノードを最大1回ずつしか訪問しないため、時間計算量は O(min(N1, N2)) です（N1・N2 はそれぞれの木のノード数）。また、再帰呼び出しの深さは木の高さに依存するため、必要な追加メモリ（再帰スタック）は O(min(H1, H2)) となります。

まとめ

フリップ等価性の判定は、「左右どちらの子と対応付けるか」を各ノードで柔軟に選べるように拡張した、通常の木の等価性チェックだと考えると理解しやすいでしょう。再帰のベースケース（両方 null／片方だけ null／値の不一致）を正しく押さえることが、バグのない実装への近道です。