C++で二分木の最も深い葉ノードの値の合計を求める方法

はじめに

二分木（バイナリツリー）が与えられたとき、その中で最も深い位置にある葉ノード（deepest leaves）の値の合計を求めることを考えます。例えば、次のような二分木があるとします。

この場合、最も深い葉ノードは 7 と 4 であり、出力は 11 になります。

解法のアプローチ

この問題は、深さ優先探索（DFS）を用いて各レベルごとのノードの値の合計を記録し、最後に最大深度に対応する合計を取得することで解けます。具体的には、以下の手順に従います。

• レベルごとの合計を保持するマップ m と、最大深度を記録する変数 maxDepth を定義する
• ノードとレベルを受け取る再帰メソッド solve() を定義する（レベルの初期値は 0）
• ノードが存在しない場合は何もせずに処理を終了する
• maxDepth を現在のレベルと既存の maxDepth の大きい方で更新する
• m[level] に現在のノードの値を加算する
• 左の子ノードに対して solve(node->left, level + 1) を呼び出す
• 右の子ノードに対して solve(node->right, level + 1) を呼び出す
• main 関数では maxDepth = 0 に初期化した上で solve(root, 0) を実行する
• 最後に 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;
   }
};
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(){
   TreeNode *root = new TreeNode(1);
   root->left = new TreeNode(2);
   root->right = new TreeNode(3);
   root->left->left = new TreeNode(4);
   root->left->right = new TreeNode(5);
   root->right->right = new TreeNode(6);
   root->right->right->right = new TreeNode(4);
   root->left->left->left = new TreeNode(7);
   Solution ob;
   cout << (ob.deepestLeavesSum(root));
}

入力

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

出力

11

まとめ

このアルゴリズムでは、すべてのノードを一度だけ訪問するため、時間計算量は O(n)、マップが保持するエントリ数は木の深さに依存するため空間計算量も効率的です。DFSによる再帰的なアプローチを採用することで、最も深い葉ノードの合計をシンプルかつ確実に求めることができます。