原文:
给定一个 n 元树，打印所有节点数为奇数和偶数的级别。
示例:
for example consider the following tree
1 - level 1
/ \
2 3 - level 2
/ \ \
4 5 6 - level 3
/ \ /
7 8 9 - level 4
the levels with odd number of nodes are: 1 3 4
the levels with even number of nodes are: 2
注:级别号从 1 开始。也就是说，根节点处于级别 1。
接近:
- 将所有连接节点插入二维向量树。
- 在树上运行 ，使高度【节点】= 1 高度【父节点】
- 完成 dfs 遍历后，对于每个节点的级别，将 count[]数组增加 1。
- 从第一级迭代到最后一级，将 count[]值为奇数的所有节点打印出来，得到奇数个节点的级别。
- 从第一级迭代到最后一级，将 count[]值为偶数的所有节点打印出来，得到偶数个节点的级别。
下面是上述方法的实现:
c
// c program to print all levels
// with odd and even number of nodes
#include
using namespace std;
// function for dfs in a tree
void dfs(int node, int parent, int height[], int vis[],
vector tree[])
{
// calculate the level of every node
height[node] = 1 height[parent];
// mark every node as visited
vis[node] = 1;
// iterate in the subtree
for (auto it : tree[node]) {
// if the node is not visited
if (!vis[it]) {
// call the dfs function
dfs(it, node, height, vis, tree);
}
}
}
// function to insert edges
void insertedges(int x, int y, vector tree[])
{
tree[x].push_back(y);
tree[y].push_back(x);
}
// function to print all levels
void printlevelsoddeven(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 ) {
// count number of nodes
// in every level
if (vis[i])
mark[height[i]] ;
// find the maximum height of tree
maxlevel = max(height[i], maxlevel);
}
// print odd number of nodes
cout << "the levels with odd number of nodes are: ";
for (int i = 1; i <= maxlevel; i ) {
if (mark[i] % 2)
cout << i << " ";
}
// print even number of nodes
cout << "\nthe levels with even number of nodes are: ";
for (int i = 1; i <= maxlevel; i ) {
if (mark[i] % 2 == 0)
cout << i << " ";
}
}
// driver code
int main()
{
// construct the tree
/* 1
/ \
2 3
/ \ \
4 5 6
/ \ /
7 8 9 */
const int n = 9;
vector tree[n 1];
insertedges(1, 2, tree);
insertedges(1, 3, tree);
insertedges(2, 4, tree);
insertedges(2, 5, tree);
insertedges(5, 7, tree);
insertedges(5, 8, tree);
insertedges(3, 6, tree);
insertedges(6, 9, tree);
int height[n 1];
int vis[n 1] = { 0 };
height[0] = 0;
// call the dfs function
dfs(1, 0, height, vis, tree);
// function to print
printlevelsoddeven(n, vis, height);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program to print all levels
// with odd and even number of nodes
import java.util.*;
@suppresswarnings("unchecked")
class gfg{
// function for dfs in a tree
static void dfs(int node, int parent,
int []height, int []vis,
arraylist []tree)
{
// calculate the level of every node
height[node] = 1 height[parent];
// mark every node as visited
vis[node] = 1;
// iterate in the subtree
for(int it : (arraylist)tree[node])
{
// if the node is not visited
if (vis[it] == 0)
{
// call the dfs function
dfs(it, node, height, vis, tree);
}
}
}
// function to insert edges
static void insertedges(int x, int y,
arraylist []tree)
{
tree[x].add(y);
tree[y].add(x);
}
// function to print all levels
static void printlevelsoddeven(int n, int []vis,
int []height)
{
int []mark = new int[n 1];
arrays.fill(mark, 0);
int maxlevel = 0;
for(int i = 1; i <= n; i )
{
// count number of nodes
// in every level
if (vis[i] != 0)
mark[height[i]] ;
// find the maximum height of tree
maxlevel = math.max(height[i], maxlevel);
}
// print odd number of nodes
system.out.print("the levels with odd "
"number of nodes are: ");
for(int i = 1; i <= maxlevel; i )
{
if (mark[i] % 2 != 0)
{
system.out.print(i " ");
}
}
// print even number of nodes
system.out.print("\nthe levels with even "
"number of nodes are: ");
for(int i = 1; i <= maxlevel; i )
{
if (mark[i] % 2 == 0)
{
system.out.print(i " ");
}
}
}
// driver code
public static void main(string []s)
{
// construct the tree
/* 1
/ \
2 3
/ \ \
4 5 6
/ \ /
7 8 9 */
int n = 9;
arraylist []tree = new arraylist[n 1];
for(int i = 0; i < n 1; i )
{
tree[i] = new arraylist();
}
insertedges(1, 2, tree);
insertedges(1, 3, tree);
insertedges(2, 4, tree);
insertedges(2, 5, tree);
insertedges(5, 7, tree);
insertedges(5, 8, tree);
insertedges(3, 6, tree);
insertedges(6, 9, tree);
int []height = new int[n 1];
int []vis = new int[n 1];
arrays.fill(vis, 0);
height[0] = 0;
// call the dfs function
dfs(1, 0, height, vis, tree);
// function to print
printlevelsoddeven(n, vis, height);
}
}
// this code is contributed by pratham76
python 3
# python3 program to print all levels
# with odd and even number of nodes
# function for dfs in a tree
def dfs(node, parent, height, vis, tree):
# calculate the level of every node
height[node] = 1 height[parent]
# mark every node as visited
vis[node] = 1
# iterate in the subtree
for it in tree[node]:
# if the node is not visited
if not vis[it]:
# call the dfs function
dfs(it, node, height, vis, tree)
# function to insert edges
def insertedges(x, y, tree):
tree[x].append(y)
tree[y].append(x)
# function to print all levels
def printlevelsoddeven(n, vis, height):
mark = [0] * (n 1)
maxlevel = 0
for i in range(1, n 1):
# count number of nodes in every level
if vis[i]:
mark[height[i]] = 1
# find the maximum height of tree
maxlevel = max(height[i], maxlevel)
# print odd number of nodes
print("the levels with odd number",
"of nodes are: ", end = "")
for i in range(1, maxlevel 1):
if mark[i] % 2:
print(i, end = " ")
# print even number of nodes
print("\nthe levels with even number",
"of nodes are: ", end = "")
for i in range(1, maxlevel 1):
if mark[i] % 2 == 0:
print(i, end = " ")
# driver code
if __name__ == "__main__":
# construct the tree
n = 9
tree = [[] for i in range(n 1)]
insertedges(1, 2, tree)
insertedges(1, 3, tree)
insertedges(2, 4, tree)
insertedges(2, 5, tree)
insertedges(5, 7, tree)
insertedges(5, 8, tree)
insertedges(3, 6, tree)
insertedges(6, 9, tree)
height = [0] * (n 1)
vis = [0] * (n 1)
# call the dfs function
dfs(1, 0, height, vis, tree)
# function to print
printlevelsoddeven(n, vis, height)
# this code is contributed by rituraj jain
c
// c# program to print all levels
// with odd and even number of nodes
using system;
using system.collections;
class gfg{
// function for dfs in a tree
static void dfs(int node, int parent,
int []height, int []vis,
arraylist []tree)
{
// calculate the level of every node
height[node] = 1 height[parent];
// mark every node as visited
vis[node] = 1;
// iterate in the subtree
foreach (int it in tree[node])
{
// if the node is not visited
if (vis[it] == 0)
{
// call the dfs function
dfs(it, node, height, vis, tree);
}
}
}
// function to insert edges
static void insertedges(int x, int y,
arraylist []tree)
{
tree[x].add(y);
tree[y].add(x);
}
// function to print all levels
static void printlevelsoddeven(int n, int []vis,
int []height)
{
int []mark = new int[n 1];
array.fill(mark, 0);
int maxlevel = 0;
for(int i = 1; i <= n; i )
{
// count number of nodes
// in every level
if (vis[i] != 0)
mark[height[i]] ;
// find the maximum height of tree
maxlevel = math.max(height[i], maxlevel);
}
// print odd number of nodes
console.write("the levels with odd "
"number of nodes are: ");
for(int i = 1; i <= maxlevel; i )
{
if (mark[i] % 2 != 0)
{
console.write(i " ");
}
}
// print even number of nodes
console.write("\nthe levels with even "
"number of nodes are: ");
for(int i = 1; i <= maxlevel; i )
{
if (mark[i] % 2 == 0)
{
console.write(i " ");
}
}
}
// driver code
static void main()
{
// construct the tree
/* 1
/ \
2 3
/ \ \
4 5 6
/ \ /
7 8 9 */
int n = 9;
arraylist []tree = new arraylist[n 1];
for(int i = 0; i < n 1; i )
{
tree[i] = new arraylist();
}
insertedges(1, 2, tree);
insertedges(1, 3, tree);
insertedges(2, 4, tree);
insertedges(2, 5, tree);
insertedges(5, 7, tree);
insertedges(5, 8, tree);
insertedges(3, 6, tree);
insertedges(6, 9, tree);
int []height = new int[n 1];
int []vis = new int[n 1];
array.fill(vis, 0);
height[0] = 0;
// call the dfs function
dfs(1, 0, height, vis, tree);
// function to print
printlevelsoddeven(n, vis, height);
}
}
// this code is contributed by rutvik_56
java 描述语言
output:
the levels with odd number of nodes are: 1 3 4
the levels with even number of nodes are: 2
时间复杂度:o(n) t3】辅助空间 : o(n)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
