C++で2つの木（二分木）が同一かどうかを判定する方法

この問題では、2つの二分木が与えられます。私たちの課題は、この2つの木が同一であるかどうかを判定するコードを書くことです。

2つの木が「同一」であるとは、すべての対応するノードが同じ値を持ち、まったく同じ位置（構造・向き）に配置されている状態を指します。

例

上の2つの木は、各ノードの値も配置位置も完全に一致しているため、同一の木であると言えます。

同一性判定の考え方

2つの木が同一かどうかを調べるには、両方の木をルートから順番にたどりながら、対応するノード同士を1つずつ比較していきます。比較の途中で値が異なるノードが見つかった場合は、その時点で「同一ではない」と判定して処理を終了します。逆に、すべてのノードの比較が完了した場合、または両方の木が空（NULL）であれば「同一である」と判定します。

アルゴリズムの手順は次のとおりです。

• 両方のノードがNULLの場合：1（同一）を返す
• 両方のノードがNULL以外の場合：「データの値が等しい」かつ「左部分木が同一」かつ「右部分木が同一」であるかを再帰的に確認する
• 片方のノードのみがNULLの場合：0（同一ではない）を返す

C++による実装例

上記の解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;
class node{
    public:
    int data;
    node* left;
    node* right;
};
node* insertNode(int data){
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
    return(Node);
}
int isIdenticalTrees(node* tree1, node* tree2){
    if (tree1 == NULL && tree2 == NULL)
        return 1;
    if (tree1 != NULL && tree2 != NULL){
        return ( tree1->data == tree2->data
            && isIdenticalTrees(tree1->left, tree2->left)
            && isIdenticalTrees(tree1->right, tree2->right) );
    }
    return 0;
}
int main(){
    node *root1 = insertNode(4);
    node *root2 = insertNode(4);
    root1->left = insertNode(5);
    root1->right = insertNode(0);
    root1->left->left = insertNode(1);
    root1->left->right = insertNode(9);
    root1->right->left = insertNode(7);
    root2->left = insertNode(5);
    root2->right = insertNode(0);
    root2->left->left = insertNode(1);
    root2->left->right = insertNode(9);
    root2->right->left = insertNode(7);
    cout<<"Both the given trees are ";
    if(isIdenticalTrees(root1, root2))
        cout<<"identical";
    else
        cout<<"not identical";
    return 0;
}

出力

Both the given trees are identical

計算量

時間計算量：O(n)（nはノードの総数。すべてのノードを1度ずつ訪問するため）
空間計算量：O(h)（hは木の高さ。再帰呼び出しのスタック領域に依存します）