【C++】二分木の最も深い葉ノードの値の合計を求めるアルゴリズム

本記事では、二分木（バイナリツリー）が与えられたときに、最も深い階層にある葉ノード（子を持たないノード）の値の合計を求めるアルゴリズムを、C++のコード例とともにわかりやすく解説します。

問題の概要

例えば、以下のような二分木が与えられたとします。

この木の場合、最も深い葉ノードは「7」と「8」であるため、求める出力は 7 + 8 = 15 となります。

解法のアプローチ

この問題は、DFS（深さ優先探索）による再帰的な走査と、各深度ごとの値の合計を記録するマップ（map）を組み合わせることで、シンプルかつ効率的に解くことができます。

アルゴリズムの手順

1. 深さごとの合計値を格納するマップ m と、最大深度を記録する変数 maxDepth を用意します。
2. 再帰関数 solve() を定義します。この関数はノードと現在のレベル（初期値は0）を引数として受け取ります。
3. ノードが存在しない場合（NULLの場合）は、そこで処理を終了して呼び出し元へ戻ります。
4. maxDepth を現在のレベルと比較し、より大きい方の値で更新します。
5. 現在のレベルの合計 m[level] に、そのノードの値を加算します。
6. 左の子ノードに対して solve(node->left, level + 1) を呼び出します。
7. 右の子ノードに対して solve(node->right, level + 1) を呼び出します。
8. メイン処理では、maxDepth を0で初期化した後、solve(root, 0) を実行します。
9. 最後に m[maxDepth] を返すことで、最も深い葉ノードの合計値が得られます。

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 maxDepth;
    map <int, int> m;
    void solve(TreeNode* node, int level = 0){
        if(!node)return;
        maxDepth = max(level, maxDepth);
        m[level] += node->val;
        solve(node->left, level + 1);
        solve(node->right, level + 1);
    }
    int deepestLeavesSum(TreeNode* root) {
        maxDepth = 0;
        m.clear();
        solve(root);
        return m[maxDepth];
    }
};
main(){
    vector<int> v = {1,2,3,4,5,NULL,6,7,NULL,NULL,NULL,NULL,8};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << (ob.deepestLeavesSum(root));
}

実行結果

入力

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

出力

15

まとめ

この手法のポイントは、再帰的に全ノードを訪問しながら、各深度の値をマップに集約している点です。これにより、どれだけ木が深くなっても、最も深い層の合計を簡単に取得できます。時間計算量は O(n)、空間計算量も O(n) であり、一般的な二分木の規模に対して十分高速に動作します。LeetCodeなどの競技プログラミングでも頻出のパターンですので、ぜひマスターしておきましょう。