C++で文字列として表されるツリーのk番目のレベルのノードの積

文字列形式のデータを持つノードのツリーで与えられ、タスクは、バイナリツリーのk番目のレベルでノードの積を見つけることです。ツリーのすべてのノードには、データ部分、左サブツリーの左ポインタ、右サブツリーの右ポインタの3つが含まれています。

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

二分木で、k=2の値が与えられたとしましょう

したがって、レベル2のノードは-40、50、60

製品=40* 50 * 60 =1,20,000

入力

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

出力

product of nodes at level k = 12

入力

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

出力

product of nodes at level k = 72

アルゴリズム

Start
Step 1→ Declare function to calculate nodes at k-th level
   int product(string tree, int k)
      Declare int level = -1
      Declare int product = 1
      Declare int size = tree.length()
      Loop For int i = 0 and i < size and i++
         IF tree[i] = '('
            Set level++
         End
         Else IF tree[i] = ')'
            Set level—
         End
         Else
            IF level = k
               Set product *= (tree[i] - '0')
            End
         End
      End
      return product
Step 2→ In main()
   Declare string tree = "(1(2(3()())(4()(5()())))(6(7()())(8()())))"
   Declare int k = 1
   Call product(tree, k)
Stop

例

#include <bits/stdc++.h>
using namespace std;
//finding product at kth level
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