นับโหนดในทรีที่กำหนดซึ่งผลรวมของหลักน้ำหนักเป็นเลขคี่ใน 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 บนกราฟของทรีเพื่อสำรวจและตรวจสอบผลรวมของตัวเลขน้ำหนักของแต่ละโหนด หากเป็นเลขคี่ ใช้ vectorsNode_Weight(100) และ edge_graph[100] สองตัวเพื่อจุดประสงค์นี้

• เริ่มต้น Node_Weight[] ด้วยน้ำหนักของโหนด

• สร้างต้นไม้โดยใช้ vector edge_graph

• หาผลรวมของตัวแปรโกลบอลและเริ่มต้นด้วย 0

• ฟังก์ชัน sum_total(int check) ใช้จำนวนเต็มและส่งกลับผลรวมของตัวเลข

• นำผลรวมเริ่มต้นเป็นจำนวนทั้งหมด=0

• ใช้ while loop คำนวณตัวเลขทางขวาสุดเป็นเช็ค % 10 และเพิ่มเป็นยอดรวม ลดการตรวจสอบลง 10

• คืนยอดรวมเป็นยอดเช็ค

• ฟังก์ชัน odd_weight(โหนด int, รูท int) รับโหนดและโหนดรูทของต้นไม้และส่งคืนการนับโหนดในทรีที่ระบุซึ่งผลรวมของตัวเลขน้ำหนักเป็นเลขคี่

• คำนวณผลรวม =sum_total(Node_Weight[node]) เป็นผลรวมของน้ำหนักของโหนด

• หากยอดรวม%2==1 เป็นเลขคี่ ให้เพิ่มผลรวม

• หากยอดรวม%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