พิมพ์ Levels ที่มีจำนวนโหนดคี่และคู่ใน C++

ในปัญหานี้ เราจะได้รับ tree และต้องพิมพ์ levels ทั้งหมดที่มีจำนวนโหนดเป็นเลขคี่และเลขคู่

ตัวอย่างเพื่อความเข้าใจ

Output -

Levels with odd number of nodes: 1, 3, 4
Levels with even number of nodes: 2

คำอธิบาย - Level แรกมี 1 องค์ประกอบ (คี่) Level ที่ 2 มี 2 องค์ประกอบ (คู่) Level ที่ 3 มี 3 องค์ประกอบ (คี่) และ Level ที่ 4 มี 1 องค์ประกอบ (คู่)

ตอนนี้เพื่อแก้ปัญหานี้ เราต้องหาจำนวนโหนดที่แต่ละ level และพิมพ์ level คี่คู่ตามลำดับ

เราจะทำตามขั้นตอนต่อไปนี้เพื่อหาคำตอบ:

ขั้นตอนที่ 1 - รัน search algorithm สำหรับทุก level โดยใช้ height[node] = 1 + height[parent]

ขั้นตอนที่ 2 - สำหรับทุก level ให้เก็บจำนวนโหนดที่ level นั้น

ขั้นตอนที่ 3 - วนลูปผ่าน array ที่มีองค์ประกอบ และพิมพ์ที่ level คี่และคู่

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

void traversal(int node, int parent, int height[], int vis[], vector<int> tree[]) {
    height[node] = 1 + height[parent];
    vis[node] = 1;
    for (auto it : tree[node]) {
        if (!vis[it]) {
            traversal(it, node, height, vis, tree);
        }
    }
}

void insert(int x, int y, vector<int> tree[]) {
    tree[x].push_back(y);
    tree[y].push_back(x);
}

void evenOddLevels(int N, int vis[], int height[]) {
    int mark[N + 1];
    memset(mark, 0, sizeof mark);
    int maxLevel = 0;
    for (int i = 1; i <= N; i++) {
        if (vis[i])
            mark[height[i]]++;
        maxLevel = max(height[i], maxLevel);
    }
    cout << "The levels with odd number of nodes are: ";
    for (int i = 1; i <= maxLevel; i++) {
        if (mark[i] % 2)
            cout << i << " ";
    }
    cout << "\nThe levels with even number of nodes are: ";
    for (int i = 1; i <= maxLevel; i++) {
        if (mark[i] % 2 == 0)
            cout << i << " ";
    }
}

int main() {
    const int N = 9;
    vector<int> tree[N + 1];
    insert(1, 2, tree);
    insert(1, 3, tree);
    insert(2, 4, tree);
    insert(2, 5, tree);
    insert(5, 7, tree);
    insert(5, 8, tree);
    insert(3, 6, tree);
    insert(6, 9, tree);
    int height[N + 1];
    int vis[N + 1] = {0};
    height[0] = 0;
    traversal(1, 0, height, vis, tree);
    evenOddLevels(N, vis, height);
    return 0;
}

ผลลัพธ์

The levels with odd number of nodes are: 1 3 4
The levels with even number of nodes are: 2