C++で二分木のコイン配布問題を解く方法

問題の概要

N個のノードを持つ二分木のルートが与えられます。各ノードには node.val 枚のコインが置かれており、木全体のコインの総数はちょうどN枚です。1回の操作では、隣接する2つのノード（親子関係にあるノード）を選び、1枚のコインだけを一方から他方へ移動できます（親から子への移動、子から親への移動のどちらも可能です）。すべてのノードがちょうど1枚のコインを持つ状態にするために必要な最小の操作回数を求めましょう。

具体例

例として、次のような木を考えてみます。

• ルート：0枚
• 左の子：3枚
• 右の子：0枚

この場合の出力は 3 になります。まず左の子から2枚のコインをルートへ送ります（コイン1枚につき1操作なので、計2操作）。次にルートから右の子へ1枚のコインを移動します。合計で3操作となります。

解法のアプローチ

この問題は、木を再帰的に走査することで効率よく解けます。手順は以下の通りです。

• 再帰メソッド solve() を定義し、引数としてノード root を受け取る
• root がNULLの場合は 0 を返す
• l := solve(ルートの左の子)
• r := solve(ルートの右の子)
• ans += |l| + |r|
• l + r + ノードの値 − 1 を返す
• main側では ans := 0 と初期化し、solve(root) を呼び出した後、ans を返す

アルゴリズムのポイント

solve() の戻り値は、「その部分木が親方向へ送り出すべきコインの余剰（正の値）」または「親から受け取るべきコインの不足（負の値）」を表しています。ある辺（エッジ）をコインが通過しなければならない回数は、その部分木における過不足の絶対値に等しいため、各ノードで |l| + |r| を累積していくことで、必要な操作回数の合計が求まります。各ノードを一度だけ訪問するため、時間計算量は O(N) と非常に効率的です。

実装例（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:
    int ans;
    int solve(TreeNode* root){
        if(!root)return 0;
        int l = solve(root->left);
        int r = solve(root->right);
        ans += abs(l) + abs(r);
        return l + r + root->val - 1;
    }
    int distributeCoins(TreeNode* root) {
        ans = 0;
        solve(root);
        return ans;
    }
};
main(){
    vector<int> v = {0,3,0};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << (ob.distributeCoins(root));
}

入力

[0,3,0]

出力

3

まとめ

二分木のコイン配布問題は、「部分木ごとのコインの過不足をボトムアップに伝播させる」という再帰的な発想が鍵となります。各ノードで子部分木からの結果を絶対値として加算するだけで答えが得られるため、シンプルでありながら強力な手法です。同様のパターンは、木の構造に関する多くの集約問題にも応用できます。