题目要求

解题思路

题目要求是求出每一层的叶子节点的个数，首先考虑存储方式，你可以选择用vector<int>来存储，然后使用layer和num数组分别存放当前节点的层数和当前层数叶子节点总数；你也可以用vector<node>来存储，那么node这个结构体你就可以把层数放进去，无需单独创建layer数组，至于后面输出每一层的叶子节点，只能再去遍历一遍，可以选择用bfs遍历，用一个count来记录一层的叶子节点，每层结束你就输出count的值。

确定好存储方式后，可以用bfs或者dfs实现，具体细节如下。

代码实现

• dfs

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<sstream>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;

constexpr auto MAXN = 100;

vector<int> f[MAXN];      //用变长数组存储
vector<int> layer(MAXN);  //表示当前节点处在哪一层
vector<int> num(MAXN);        //表示当前层数的叶子节点个数
int maxlevel=0;             //表示最大的层数，即这棵树一共有几层

//lay表示层数
void dfs(int index,int lay)
{
    if(f[index].size()==0)
    {
        num[lay]++;
        maxlevel=max(maxlevel,lay);
    }
    for(int i=0;i<f[index].size();++i)
    {
        dfs(f[index][i],lay+1);
    }
}

int main()
{
#ifdef ONLINE_JUDGE                
#else    
    freopen("1.txt", "r", stdin);
#endif 
    int n,m;

    cin>>n>>m;

    int father,temp,child;

    for(int i=0;i<m;++i)
    {
        cin>>father>>temp;
        for(int j=0;j<temp;++j)
        {
            cin>>child;
            f[father].push_back(child);
        }
    }

    dfs(1,1);
    for(int i=1;i<=maxlevel;++i)
    {
        if(i==1)
        {
            cout<<num[i];
        }
        else
        {
            cout<<" "<<num[i];
        }
    }

    system("pause");
    return 0;
}

• bfs

/*
 * @filename: 
 * @description: 
 * @author: 可爱
 * @lastEditors: cute
 * @Date: 2022-05-02 21:34:32
 * @LastEditTime: 2022-05-05 22:27:03
 * @Copyright: 此处写项目版本号
 */

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<sstream>
#include<algorithm>
#pragma warning(disable:4996)
using namespace std;

constexpr auto MAXN = 100;

vector<int> f[MAXN];
vector<int> layer(MAXN);  //表示当前节点处在哪一层
vector<int> num(MAXN);        //表示当前层数的叶子节点个数
int maxlevel=0;

void bfs()
{
    queue<int> q;
    q.push(1);
    layer[1]=1;

    while(!q.empty())
    {
        int index=q.front();
        q.pop();

        maxlevel = max(layer[index],maxlevel);
        if(f[index].size()==0)
        {
            //说明该节点是叶子节点
            num[layer[index]]++;
        }
        else
        {   
            //说明不是叶子节点，那就正常入队，把当前节点的孩子节点入队即可
            for(int i=0;i<f[index].size();++i)
            {
                q.push(f[index][i]);
                layer[f[index][i]]=layer[index]+1;
            }

        }
    }
}

int main()
{
#ifdef ONLINE_JUDGE                
#else    
    freopen("1.txt", "r", stdin);
#endif 
    int n,m;

    cin>>n>>m;

    int father,temp,child;

    for(int i=0;i<m;++i)
    {
        cin>>father>>temp;
        for(int j=0;j<temp;++j)
        {
            cin>>child;
            f[father].push_back(child);
        }
    }

    bfs();
    for(int i=1;i<=maxlevel;++i)
    {
        if(i==1)
        {
            cout<<num[i];
        }
        else
        {
            cout<<" "<<num[i];
        }
    }

    system("pause");
    return 0;
}