C++で二分木の同じ階層にある葉ノードの合計値の積を求める方法

概要

与えられた二分木（バイナリツリー）に対して、次の値を返すプログラムを考えます。

• 各階層（レベル）について、その階層に葉ノードが存在する場合は、すべての葉ノードのデータの合計を計算します。存在しない場合はその階層を無視します。

• 計算されたすべての階層ごとの合計値を掛け合わせ、その結果を返します。

入力例1

次の木のルート
      3
     / \
    8   6
         \
          10

出力例1

80

第1階層には葉ノードがありません。第2階層には葉ノード「8」が1つあり、第3階層にも葉ノード「10」が1つあります。したがって、結果は 8 × 10 = 80 となります。

入力例2

次の木のルート
             3
           /   \
           8   6
          / \   \
         9  7   10
           / \  / \
           2 12 5 11

出力例2

270

最初の2つの階層には葉ノードがありません。第3階層には葉ノード「9」が1つだけあり、最下層には「2」「12」「5」「11」の4つの葉ノードがあります。したがって、結果は 9 × (2 + 12 + 5 + 11) = 270 となります。

解法アプローチ

単純な解法

最もシンプルな方法は、上から下へすべての階層に対して再帰的に葉ノードの合計を計算し、その後、葉ノードが存在する階層の合計値同士を掛け合わせることです。ただし、この方法の時間計算量は O(n²) となり、大きな木では非効率です。

効率的な解法

より効率的な方法は、キューを使用したレベル順走査（幅優先探索）を実装することです。走査を行いながら、各階層を個別に処理します。処理対象の各階層について、葉ノードが存在するかどうかを確認し、存在する場合はその階層の葉ノードの合計を計算します。最後に、すべての合計値の積を返します。この方法なら時間計算量は O(n) に抑えられます。

実装例

/* 二分木の同じ階層にあるすべての葉ノードのデータの合計を求め、
   得られた全階層の合計値の積を計算する反復型C++プログラム */
#include <bits/stdc++.h>
using namespace std;
// 二分木のノード構造体
typedef struct Node1 {
   int data1;
   struct Node1 *left1, *right1;
} Node1;
// ノードが木の葉であるかどうかを判定するヘルパー関数
bool isLeaf(Node1* root1){
   return (!root1->left1 && !root1->right1);
}
/* 各階層のすべての葉ノードの合計を計算し、
   合計値の積を返す関数 */
int sumAndMultiplyLevelData(Node1* root1){
   // 木が空の場合
   if (!root1)
      return 0;
   int mul1 = 1; /* 結果を格納する変数 */
   // レベル順走査用の空のキューを作成
   queue<Node1*> q1;
   // ルートをキューに追加
   q1.push(root1);
   // 木のレベル順走査を実行
   while (1) {
      // NodeCount1（キューのサイズ）は現在の階層の
      // ノード数を表す
      int NodeCount1 = q1.size();
      // 現在の階層にノードがない場合、処理終了
      if (NodeCount1 == 0)
         break;
      // 現在の階層の葉ノード合計を初期化
      int levelSum1 = 0;
      // 現在の階層で葉ノードが見つかったかどうかを示すフラグ
      bool leafFound1 = false;
      // 現在の階層のすべてのノードを取り出し、
      // 次の階層のノードをすべてキューに追加
      while (NodeCount1 > 0) {
         // 現在の階層の次のノードを処理
         Node1* node1 = q1.front();
         /* ノードが葉の場合、階層の合計を更新 */
         if (isLeaf(node1)) {
            leafFound1 = true;
            levelSum1 += node1->data1;
         }
         q1.pop();
         // ノードの子をキューに追加
         if (node1->left1 != NULL)
            q1.push(node1->left1);
         if (node1->right1 != NULL)
            q1.push(node1->right1);
         NodeCount1--;
      }
      // 少なくとも1つの葉ノードが見つかった場合、
      // 結果に階層の合計を掛ける
      if (leafFound1)
         mul1 *= levelSum1;
   }
   return mul1; // 結果を返す
}
// 新しい木のノードを作成するユーティリティ関数
Node1* newNode(int data1){
   Node1* temp1 = new Node1;
   temp1->data1 = data1;
   temp1->left1 = temp1->right1 = NULL;
   return temp1;
}
// 上記の関数をテストするドライバープログラム
int main(){
   Node1* root1 = newNode(3);
   root1->left1 = newNode(8);
   root1->right1 = newNode(6);
   root1->left1->right1 = newNode(7);
   root1->left1->left1 = newNode(9);
   root1->left1->right1->left1 = newNode(2);
   root1->left1->right1->right1 = newNode(12);
   root1->right1->right1 = newNode(10);
   root1->right1->right1->left1 = newNode(5);
   root1->right1->right1->right1 = newNode(11);
   cout << "最終的な積の値 = "
   << sumAndMultiplyLevelData(root1) <<endl;
   return 0;
}

出力結果

最終的な積の値 = 270