欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

1004. Counting Leaves

程序员文章站 2022-06-11 15:11:51
...

题目信息:

1004. Counting Leaves

题目的意思是找出树中每一层的叶节点个数。
个人觉得难点在寻找每一层有哪些结点,或者说每一个结点在哪一层。题主的做法是用一个队列来帮助我们记录每一个叶节点的层数。
需要注意的是,输入的数据可能是乱序的,也就是头一列可能不是叶节点的,这个也是一个难点。

/* 题目:1004    */
/* 作者:ChanWunsam  */
/* 时间:2017.12.19  */
#include <cstdio>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

struct TNode{
  int childNum;
  int height;
  int *child;
};
struct TNode FMTree[101];

int main()
{
  int N, M, ID, childNum, childID, i, j, queue[101], front, rear, cnt[100], H, MaxH;
  cin>>N>>M;

  /* 初始化家庭树 */
  for(i=0; i<=N; i++)
  {
    FMTree[i].childNum=0;
    FMTree[i].height=0;
    cnt[i]=0;
  }

  /* 输入数据 */
  for(i=0; i<M; i++)
  {
    cin>>ID;
    cin>>childNum;
    FMTree[ID].childNum=childNum;
    //cout<<"ID:"<<ID<<" "<<FMTree[ID].height<<endl;

    FMTree[ID].child=(int *)malloc(childNum * sizeof(int));
    for(j=0; j<childNum; j++)
    {
      cin>>childID;
      FMTree[ID].child[j]=childID;
    }
  }

  /* 建立树层 */
  front=rear=0;
  queue[rear++]=1;      /* 根节点,很重要 */
  while(rear-front)
  {
    ID=queue[front++];
    for(i=0; i<FMTree[ID].childNum; i++)
    {
      j=FMTree[ID].child[i];
      queue[rear++]=j;
      FMTree[j].height=FMTree[ID].height+1; 
    }
  }

  /* 寻找无子树结点 */
  H=MaxH=0;
  for(i=1; i<=N; i++)
  {
    H=FMTree[i].height;
    if(!FMTree[i].childNum)
      cnt[H]++;
    if(H>MaxH)
      MaxH=H;
  }

  /* 输出值 */
  cout<<cnt[0];
  for(i=1; i<=MaxH; i++)
    cout<<" "<<cnt[i];

    return 0;
}

虽然时间复杂度依旧被暴捶,但是好在这算是题主真正意义上独立解决的一个问题(不过中间卡在了乱序的那个地方去寻找思路了),而且思路也和大佬们差不多。还是有点小满足的。

1004. Counting Leaves


上星期欠的债算是补了一部分了。。。。