C ++で重みの桁の合計が奇数である、指定されたツリー内のノードをカウントします

ノードの重みを持つ二分木が与えられます。目標は、重みを持つノードの数を見つけて、その重みの桁の合計が奇数になるようにすることです。重みが12の場合、桁の合計は3であり、奇数であるため、このノードがカウントされます。

例

入力

値を入力した後に作成されるツリーを以下に示します-

出力

Count of nodes in the given tree whose sum of digits of weight is odd are: 2

説明

we are given with the tree node and the weights associated with each
node. Now we calculate the digit sum of each and every weight and check whether it's
odd or not.

入力

値を入力した後に作成されるツリーを以下に示します-

出力

Count of nodes in the given tree whose sum of digits of weight is odd are: 4

説明

we are given with the tree node and the weights associated with each
node. Now we calculate the digit sum of each and every weight and check whether it's
odd or not.

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、ツリーのグラフにDFSを適用してトラバースし、各ノードの重みの桁の合計が奇数であるかどうかを確認します。この目的のために、2つのvectorsNode_Weight（100）とedge_graph[100]を取ります。

• Node_Weight[]をノードの重みで初期化します。

• ベクトルedge_graphを使用してツリーを作成します。

• グローバル変数の合計を取り、0で初期化します。

• 関数sum_total（int check）は整数を取り、その桁の合計を返します。

• 最初の合計をtotal=0とします。

• whileループを使用して、右端の桁をチェック％10として計算し、それを合計に追加します。チェックを10減らします。

• チェックの桁の合計として合計を返します。

• 関数odd_weight（int node、int root）は、ツリーのノードとルートノードを取得し、重みの桁の合計が奇数である、指定されたツリー内のノードの数を返します。

• 合計=sum_total（Node_Weight [node]）をノードの重みの合計として計算します。

• total％2 ==1の場合、その奇数は合計をインクリメントします。

• total％2 ==1の場合、その奇数は合計をインクリメントします。

• ベクトル内の次のノードに対してodd_weight（it、node）を呼び出します。

• すべての関数の最後に、ノードの数として合計があり、桁の重みを削った合計が奇数としてあります。

例

#include <bits/stdc++.h>
using namespace std;
vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int sum = 0;
int sum_total(int check){
   int total = 0;
   while(check){
      total += check % 10;
      check = check / 10;
   }
   return total;
}
void odd_weight(int node, int root){
   int total = sum_total(Node_Weight[node]);
   if (total % 2 == 1){
      sum++;
   }
   for (int it : edge_graph[node]){
      if(it == root){
         continue;
      }
      odd_weight(it, node);
   }
}
int main(){
   //weight of the nodes
   Node_Weight[2] = 23;
   Node_Weight[1] = 141;
   Node_Weight[4] = 211;
   Node_Weight[3] = 115;
   Node_Weight[8] = 7171;
   Node_Weight[9] = 701;
   //create graph edge
   edge_graph[2].push_back(1);
   edge_graph[2].push_back(4);
   edge_graph[4].push_back(3);
   edge_graph[4].push_back(8);
   edge_graph[8].push_back(9);
   odd_weight(2, 2);
   cout<<"Count the nodes in the given tree whose sum of digits of weight is odd are: "<<sum;
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count the nodes in the given tree whose sum of digits of weight is odd are: 2