C++에서 홀수 및 짝수 노드가 있는 모든 레벨 인쇄

이 문제에서는 나무가 주어집니다. 그리고 짝수 노드와 홀수 노드가 있는 모든 레벨을 인쇄해야 합니다.

개념을 더 잘 이해하기 위해 예를 들어보겠습니다.

출력 -

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

설명 − 첫 번째 레벨은 1개의 요소(홀수), 2번째 레벨은 2개의 요소(짝수), 3번째 레벨은 3개의 요소(홀수), 4번째 레벨은 1개의 요소(짝수)를 포함합니다.

이제 이 문제를 해결합니다. 각 수준에서 노드 수를 찾고 그에 따라 짝수-홀수 수준을 인쇄해야 합니다.

우리는 해결책을 찾기 위해 다음 단계를 따를 것입니다 -

1단계 − height[node]=1+height[parent]

2단계 − 모든 레벨에 대해 해당 레벨의 노드 수를 저장합니다.

3단계 - 요소를 포함하는 배열을 반복하고 짝수 및 홀수 수준에서 인쇄합니다.

예시

#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