C++で文字列として表現された二分木のk番目のレベルにあるノードの積を求める方法

はじめに

文字列形式で表現された二分木が与えられたとき、k番目のレベルに存在するノードの値の積を求めるのが本記事の目的です。二分木の各ノードは、データ部分・左部分木を指すポインタ・右部分木を指すポインタの3つの要素で構成されています。

二分木のレベルは0から始まり、任意の正の整数nまで続きます。ここでは、レベル「k」が与えられ、そのレベルにあるノードの値の積をプログラムで計算します。

例えば、次のような二分木に対してk=2が与えられた場合を考えてみましょう。

レベル2のノードは − 40、50、60 です。

積 = 40 × 50 × 60 = 120,000

入力例1

(1(2(3()())(4()(5()())))(6(7()())(8()())))
K = 1

出力例1

product of nodes at level k = 12

入力例2

(0(5(6()())(4()(9()())))(7(1()())(3()())))
k = 2

出力例2

product of nodes at level k = 72

アルゴリズムの考え方

この問題は、木を実際に構築しなくても、文字列を直接走査することで効率的に解くことができます。文字列は括弧によって木の構造を表現しているため、次の手順で処理します。

• 文字列を左から右へ1文字ずつ走査します。
• 開き括弧「(」に遭遇したら、現在のレベルを1つ深くします（level++）。
• 閉じ括弧「)」に遭遇したら、現在のレベルを1つ浅くします（level--）。
• 数字（ノードのデータ）に遭遇したとき、現在のレベルがkと一致していれば、その値を積に乗算します。

この方法の計算量はO(n)（nは文字列の長さ）で、木を構築するための追加メモリも不要なため、非常に効率的です。

アルゴリズム

開始
ステップ1 → k番目のレベルのノードの積を計算する関数を宣言
    int product(string tree, int k)
      int level = -1 を宣言
      int product = 1 を宣言
      int size = tree.length() を宣言
      ループ: int i = 0 から i < size まで i++ ごとに
          IF tree[i] = '(' の場合
            level++ を実行
          End
          ELSE IF tree[i] = ')' の場合
            level-- を実行
          End
          ELSE の場合
            IF level = k の場合
              product *= (tree[i] - '0') を実行
            End
          End
      End
      return product
ステップ2 → main() 内で
    string tree = "(1(2(3()())(4()(5()())))(6(7()())(8()())))" を宣言
    int k = 1 を宣言
    product(tree, k) を呼び出す
終了

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
//k番目のレベルの積を求める
int product(string tree, int k){
    int level = -1;
    int product = 1;
    int size = tree.length();
    for (int i = 0; i < size; i++){
        if (tree[i] == '(')
            level++;
        else if (tree[i] == ')')
            level--;
        else{
            if (level == k)
                product *= (tree[i] - '0');
        }
    }
    return product;
}
int main(){
    string tree = "(1(2(3()())(4()(5()())))(6(7()())(8()())))";
    int k = 1;
    cout <<"product of nodes at level k = "<<product(tree, k);
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます。

product of nodes at level k = 12