不务正业系列之pat解题: 1004. Counting Leaves (30)

[yooocen]

挺有难度的一条题目，首先最简单的解法就是深度搜索了，不必过于执着父子关系，只要根结点就是第一行的数据就好，正好题目就是这种情况，用map存好关系，也不必关心是否是顺序的。

#include <cstdio>
#include <map>
#include <vector>
#include <cstdlib>
using namespace std;
map<int,vector<int> > mapList;
int levelMap[101] ={0};
void dfs(int rootId , int level)
{
    if(mapList[rootId].empty())
    {
        levelMap[level]++;
        return;
    }
        vector<int> children = mapList[rootId];
        vector<int>::iterator it = children.begin();
        for(;it!=children.end();it++)
        {
            dfs(*it, level+1); //不是++level
        }
}

int main()
{
    int n, m , rootId , k, sid;
    scanf("%d %d",&n,&m);
    int cle = n-m,cnt=0;
    while (m--) {
        scanf("%d %d",&rootId,&k);
        while (k--) {
            scanf("%d",&sid);
            mapList[rootId].push_back(sid);
        }
    }

    dfs(1,0);
    printf("%d",levelMap[0]);
    cnt+=levelMap[0];
    for(int i = 1 ; cnt<cle;i++){
        printf(" %d",levelMap[i]);
        cnt+=levelMap[i];
    }
    printf("\n");
    return 0;
}

我还搜到了另一个大佬的代码，使用构建二叉树的方式来做，比较原始，但是也非常有参考价值

#include <iostream>
using namespace std;

int count[100]={0};
int maxlevel=1;

struct childLink  //孩子链表
{
    int id;
    childLink *next;
    childLink(){next=NULL;}
};

struct Node     //树节点
{
    int childNum;
    childLink *childHead;
    Node(){childNum=0;childHead=NULL;}
}*node;

void countLeaves(int l,int id)        //嵌套求解不同层次节点中叶子节点的个数
{
    childLink *cl = node[id].childHead;
    l++;
    while(cl)
    {       
        if(maxlevel<l)maxlevel=l;
        if(node[cl->id].childNum==0)count[l]++;
        else countLeaves(l,cl->id);
        cl=cl->next;
    }
}

int main()
{
    int n,m;
    int i,j,id;
    cin>>n>>m;
    node = new Node[n+1];
    childLink *cl=0;
    for(i=0;i<m;i++)
    {
        cin>>id;
        cin>>node[id].childNum;
        for(j=0;j<node[id].childNum;j++)
        {
            cl = new childLink;
            cin>>cl->id;
            if(node[id].childHead) cl->next=node[id].childHead;
            node[id].childHead = cl;
        }
    }

    if(node[1].childNum==0){count[0]=1;maxlevel=0;}
    else 
    {
        count[0]=0;
        countLeaves(0,1);
    }
    //cout<<"maxlevel: "<<maxlevel<<endl;
    for(i=0;i<maxlevel;i++)
        cout<<count[i]<<" ";
    cout<<count[i]<<endl;
    system("PAUSE");
    return 0;
}