นับโหนดที่ผลรวมหลักของน้ำหนักเป็นเลขคี่ ใน C++

โจทย์: ให้ Binary Tree ที่โหนดมีน้ำหนักเป็นจำนวนเต็ม ต้องการนับโหนดที่ผลรวมของหลักเลข (digit sum) เป็นเลขคี่

ฟังก์ชันคำนวณผลรวมหลัก

int sum_total(int check) {
    int total = 0;
    while (check) {
        total += check % 10;
        check /= 10;
    }
    return total;
}

DFS นับโหนด

vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int sum = 0;

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);
    }
}

ตัวอย่างเต็ม

#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 /= 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() {
    Node_Weight[2] = 23;    // 2+3=5 คี่
    Node_Weight[1] = 141;   // 1+4+1=6 คู่
    Node_Weight[4] = 211;   // 2+1+1=4 คู่
    Node_Weight[3] = 115;   // 1+1+5=7 คี่
    Node_Weight[8] = 7171;  // 7+1+7+1=16 คู่
    Node_Weight[9] = 701;   // 7+0+1=8 คู่
    
    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: " << sum;
    return 0;
}

ผลลัพธ์

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

โหนดที่ผลรวมหลักเป็นคี่: 23 (5), 115 (7) = 2 โหนด