C++で2つの二分木の最初の一致しない葉を見つける方法

2つの二分木が与えられたとき、両方の木を前順(先行順)で走査した際に最初に一致しない葉ノードを見つける問題を考えます。すべての葉が一致している場合は、何も出力しません。

問題の例

次のような2つの二分木があるとします。

この場合、前順走査の順序で葉を比較していくと、最初に一致しない葉は 11 と 15 になります。

アルゴリズムの考え方

この問題は、スタックを用いた反復的な前順走査(preorder traversal)を2つの木に対して同時に実行することで解けます。ポイントは以下の通りです。

• 木ごとに独立したスタックを用意する
• スタックの先頭が葉ノードになるまで、子ノードをプッシュし続ける
• 両スタックの先頭(それぞれの木における現在の葉)を比較する
• 値が一致していれば次の葉へ進み、一致しなければその2つの葉が答えとなる

この方法なら再帰を使わずに、両木の葉を左から右へ順番に対応付けて比較できます。

C++での実装例

#include <iostream>
#include <stack>
using namespace std;
class Node {
    public:
    int data;
    Node *left, *right;
};
Node *getNode(int x) {
    Node * newNode = new Node;
    newNode->data = x;
    newNode->left = newNode->right = NULL;
    return newNode;
}
bool isLeaf(Node * t) {
    return ((t->left == NULL) && (t->right == NULL));
}
void findUnmatchedNodes(Node *t1, Node *t2) {
    if (t1 == NULL || t2 == NULL)
        return;
    stack<Node*> s1, s2;
    s1.push(t1); s2.push(t2);
    while (!s1.empty() || !s2.empty()) {
        if (s1.empty() || s2.empty() )
            return;
        Node *top1 = s1.top();
        s1.pop();
        while (top1 && !isLeaf(top1)){
            s1.push(top1->right);
            s1.push(top1->left);
            top1 = s1.top();
            s1.pop();
        }
        Node * top2 = s2.top();
        s2.pop();
        while (top2 && !isLeaf(top2)){
            s2.push(top2->right);
            s2.push(top2->left);
            top2 = s2.top();
            s2.pop();
        }
        if (top1 != NULL && top2 != NULL ){
            if (top1->data != top2->data ){
                cout << "First non matching leaves are: "<< top1->data <<" "<< top2->data<< endl;
                return;
            }
        }
    }
}
int main() {
    Node *t1 = getNode(5);
    t1->left = getNode(2);
    t1->right = getNode(7);
    t1->left->left = getNode(10);
    t1->left->right = getNode(11);
    Node * t2 = getNode(6);
    t2->left = getNode(10);
    t2->right = getNode(15);
    findUnmatchedNodes(t1,t2);
}

実行結果

First non matching leaves are: 11 15

計算量について

各ノードは最大で1回ずつスタックへのプッシュとポップが行われるため、時間計算量は O(n₁ + n₂)(n₁、n₂ はそれぞれの木のノード数)です。空間計算量は、スタックに保持されるノード数に依存し、最悪の場合で O(h₁ + h₂)(h は各木の高さ)となります。

このアルゴリズムを使えば、2つの二分木の構造が途中で異なっていても、葉の並び順に沿って効率的に差分を検出できます。