注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[NBUT] 1186 Get the Width  

2012-07-11 19:11:41|  分类: NBUT 2012 Summer |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
  • 问题描述
  • It's an easy problem. I will give you a binary tree. You just need to tell me the width of the binary tree.
    The width of a binary tree means the maximum number of nodes in a same level.
    [NBUT] 1186 Get the Width - Minary - Minary_Acdream
     

    For example, the width of binary tree above is 3.

  • 输入
  • The first line is an integer T, means the number of cases.
    Then follow T cases.
    For each case, the first line is an integer N, means the number of nodes. (1 <= N <= 10)
    Then follow N lines. Each line contains 3 integers P A B; indicate the number of this node and its two children node. If the node doesn’t have left child or right child, then replace it by -1.
    You can assume the root is 1.
  • 输出
  • For each case, output the width.
  • 样例输入
  • 1 6 4 -1 -1 2 4 5 5 -1 -1 1 2 3 6 -1 -1 3 -1 6 
  • 样例输出
  • 3 

    也是一挺水的题,不多说,直接上代码


    #include<iostream>
    #include<queue>
    #include<string.h>
    using namespace std;

    struct data
    {
    int n,depth;
    data(int n,int depth)
    {
    this ->n = n;
    this ->depth = depth;
    }
    };

    int map[2000][2];
    int cnt[2000];
    int main()
    {
    int T,n,l,r;
    queue<data> q;
    scanf("%d",&T);

    while(T--)
    {
    int N;
    scanf("%d",&N);
    memset(map,0,sizeof(map));
    memset(cnt,0,sizeof(cnt));
    for(int i = 0;i < N;i++)
    {
    scanf("%d%d%d",&n,&l,&r);
    map[n][0] = l;
    map[n][1] = r;
    }
    int max = 0;
    q.push(data(1,1));
    while(!q.empty())
    {
    data k = q.front();
    q.pop();
    cnt[k.depth] ++;
    if(k.depth > max) max = k.depth;
    if(map[k.n][0] != -1) q.push(data(map[k.n][0],k.depth + 1));
    if(map[k.n][1] != -1) q.push(data(map[k.n][1],k.depth + 1));
    }
    int m = 0;
    for(int i = 1;i <= max;i ++)
    {
    if(cnt[i] > m) m = cnt[i];
    }
    cout<<m<<endl;
    }
    return 0;
    }

  评论这张
 
阅读(121)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018