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를 적용하여 트리를 탐색하고 홀수인 경우 각 노드의 가중치 자릿수 합계를 확인합니다. 이를 위해 두 개의 vectorNode_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)는 트리의 노드와 루트 노드를 취하여 주어진 트리에서 가중치의 합이 홀수인 노드의 수를 반환합니다.

• total =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