इस समस्या में हमें एक पेड़ दिया जाता है। और हमें सभी स्तरों को सम संख्या में नोड्स और विषम संख्या में नोड्स के साथ प्रिंट करना होगा।
आइए अवधारणा को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं
आउटपुट -
Levels with odd number of nodes: 1, 3, 4 Levels with even number of nodes: 2
स्पष्टीकरण - पहले स्तर में केवल 1 तत्व (विषम), दूसरे स्तर में दो तत्व (सम) होते हैं, तीसरे स्तर में 3 तत्व (विषम) होते हैं और चौथे स्तर में 1 तत्व (सम) होता है।
अब, इस समस्या को हल करने के लिए। हमें प्रत्येक स्तर पर नोड्स की संख्या का पता लगाना होगा और उसके अनुसार सम-विषम स्तरों को प्रिंट करना होगा।
समाधान खोजने के लिए हम निम्नलिखित चरणों का पालन करेंगे -
चरण 1 -ऊंचाई[नोड]=1+ऊंचाई[पैरेंट]
. का उपयोग करके हर स्तर के लिए खोज एल्गोरिथम चलाएंचरण 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