Trong bài toán này, chúng ta được đưa ra một cái cây. Và chúng ta phải in tất cả các mức có số nút chẵn và số nút lẻ trong đó.
Hãy lấy một ví dụ để hiểu rõ hơn về khái niệm này
Đầu ra -
Levels with odd number of nodes: 1, 3, 4 Levels with even number of nodes: 2
Giải thích - Mức đầu tiên chỉ có 1 phần tử (lẻ), mức 2 chứa hai phần tử (chẵn), mức 3 chứa 3 phần tử (lẻ) và mức 4 chứa 1 phần tử (chẵn).
Bây giờ, để giải quyết vấn đề này. Chúng ta cần tìm số nút ở mỗi cấp và in các cấp chẵn-lẻ tương ứng.
Chúng tôi sẽ làm theo các bước sau để tìm ra giải pháp -
Bước 1 - Chạy thuật toán tìm kiếm cho mọi cấp độ sử dụng height [node] =1 + height [cha]
Bước 2 - Đối với mọi cấp, lưu trữ số lượng nút ở cấp đó.
Bước 3 - lặp qua mảng có chứa các phần tử và in ở cấp độ chẵn và lẻ.
Ví dụ
#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;
} Đầu ra
The levels with odd number of nodes are: 1 3 4 The levels with even number of nodes are: 2