C++で2つの二分木をマージする方法【サンプルコード付きで解説】

2つの二分木が与えられ、一方の木をもう一方の木の上に重ね合わせることを考えてみましょう。このとき、両方の木の一部のノードは互いに重なり合い、それ以外のノードは重ならずに残ります。本記事では、こうした2つの木を1つの新しい二分木へとマージする方法を解説します。

マージのルールは次の通りです。2つのノードが重なっている場合には、それらのノード値を合計したものを、マージ後のノードの新しい値とします。どちらか一方にしか存在しないノードについては、空でない側のノードをそのまま新しい木のノードとして利用します。

例えば、次のような2つの木があったとします。

これらをマージすると、結果は次のようになります。

解き方のアプローチ

この問題は、再帰処理を使うことでシンプルに解くことができます。具体的には、以下の手順に従います。

• solve() メソッドを用意します。このメソッドは、2つの木のノード n1 と n2 を引数として受け取ります。
• n1 が NULL で n2 が非 NULL の場合は n2 を返します。逆に n2 が NULL で n1 が非 NULL の場合は n1 を返します。さらに、両方とも NULL の場合には NULL を返します。
• n1 の値 := n1 の値 + n2 の値（重なったノードの値を合計）
• n1 の左の子 := solve(n1 の左の子, n2 の左の子)
• n1 の右の子 := solve(n1 の右の子, n2 の右の子)
• n1 を返します。

それでは、理解を深めるために実際の実装例を見ていきましょう。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int v){
        val = v;
        left = right = NULL;
    }
};
void inord(TreeNode *root) {
    if (root != NULL) {
        inord(root->left);
        cout << root->val << " ";
        inord(root->right);
    }
}
class Solution {
public:
    TreeNode* solve(TreeNode* n1, TreeNode* n2) {
        if(!n1 && n2)
            return n2;
        else if(!n2 && n1)
            return n1;
        else if(!n1 && !n2)
            return NULL;
        n1->val += n2->val;
        n1->left = solve(n1->left, n2->left);
        n1->right = solve(n1->right, n2->right);
        return n1;
    }
};
main(){
    TreeNode *root1 = new TreeNode(1);
    root1->left = new TreeNode(3);
    root1->right = new TreeNode(2);
    root1->left->left = new TreeNode(5);
    TreeNode *root2 = new TreeNode(2);
    root2->left = new TreeNode(1);
    root2->right = new TreeNode(3);
    root2->left->right = new TreeNode(4);
    root2->right->right = new TreeNode(7);
    Solution ob;
    TreeNode *root_res = ob.solve(root1, root2);
    inord(root_res);
}

入力

TreeNode *root1 = new TreeNode(1);
root1->left = new TreeNode(3);
root1->right = new TreeNode(2);
root1->left->left = new TreeNode(5);
TreeNode *root2 = new TreeNode(2);
root2->left = new TreeNode(1);
root2->right = new TreeNode(3);
root2->left->right = new TreeNode(4);
root2->right->right = new TreeNode(7);

出力

5 4 4 3 5 7

計算量について

このアルゴリズムでは、各ノードを一度だけ訪問するため、時間計算量は O(n) となります。ここで n は2つの木のうち大きい方のノード数です。また、再帰呼び出しの深さは木の高さに依存するため、空間計算量は最悪の場合（木が偏っているとき）O(n)、バランスの取れた木であれば O(log n) となります。

まとめ

2つの二分木のマージは、再帰を活用すれば非常に簡潔に実装できる典型的な木構造の問題です。「両方に存在するノードは値を足し合わせる」「片方にしか存在しないノードはそのまま使う」というルールを、再帰関数の条件分岐に正しく落とし込むことがポイントです。木構造の再帰処理に慣れたい初心者の方にも、ぜひ取り組んでみていただきたい練習問題と言えるでしょう。