专栏首页数据结构与算法1501 二叉树最大宽度和高度

1501 二叉树最大宽度和高度

1501 二叉树最大宽度和高度

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 白银 Silver

题目描述 Description

    给出一个二叉树,输出它的最大宽度和高度。

输入描述 Input Description

第一行一个整数n。

下面n行每行有两个数,对于第i行的两个数,代表编号为i的节点所连接的两个左右儿子的编号。如果没有某个儿子为空,则为0。

输出描述 Output Description

输出共一行,输出二叉树的最大宽度和高度,用一个空格隔开。

样例输入 Sample Input

5

2 3

4 5

0 0

0 0

0 0

样例输出 Sample Output

2 3

数据范围及提示 Data Size & Hint

n<16

默认第一个是根节点

以输入的次序为编号

2-N+1行指的是这个节点的左孩子和右孩子

注意:第二题有极端数据!

          1

          0 0

这题你们别想投机取巧了,给我老老实实搜索!

分类标签 Tags 点此展开

 1 #include<iostream>
 2 using namespace std;
 3 int root;
 4 int max_shendu=0;
 5 int max_kuandu=1;
 6 struct node
 7 {
 8     int parent;
 9     int date;
10     int lchild;
11     int rchile;
12     int sd;
13 }a[101];
14 int bl(int sd_now,int i)
15 {
16     //int flag1=0;
17     //int flag2=0;
18     a[i].sd=sd_now;
19     if(a[i].sd>max_shendu)
20     {
21         max_shendu=a[i].sd;
22     }
23     if(a[i].lchild!=0)
24     {
25     //    flag1=1;
26         bl(sd_now+1,a[i].lchild);
27     }
28     if(a[i].rchile!=0)
29     {
30     //    flag2=1;
31         bl(sd_now+1,a[i].rchile);
32     }
33     /*if(flag1==1&&flag2==1)
34     {
35         max_kuandu++;
36     }*/
37 }
38 int main()
39 {
40     int n;
41     cin>>n;
42     for(int i=1;i<=n;i++)
43     {
44         cin>>a[i].lchild>>a[i].rchile;
45         a[a[i].lchild].parent=i;
46         a[a[i].rchile].parent=i;
47     }
48     for(int i=1;i<=n;i++)
49     {
50         if(a[i].parent==0)
51         {
52             root=i;
53             break;
54         }
55     }
56     bl(0,root);
57     for(int i=0;i<=max_shendu;i++)
58     {
59         int sum=0;
60         for(int j=1;j<=n;j++)
61         {
62             if(a[j].sd==i)
63             {
64                 sum++;
65             }
66         }
67         if(sum>max_kuandu)
68         {
69             max_kuandu=sum;
70         }
71     }
72     cout<<max_kuandu<<" ";
73     cout<<max_shendu+1;
74     return 0;
75 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 查找二叉树

    【问题描述】 已知一棵二叉树用邻接表结构存储,中序查找二叉树中值为x的结点,并指出是第几个结点。例:如图二叉树的数据文件的数据格式如下 7 15 5 2 3 1...

    attack
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • 洛谷P3437 [POI2006]TET-Tetris 3D(二维线段树 标记永久化)

    对于这题来说,因为有修改操作,我们需要在外层线段树上也打标记,而且标记的形式是对一段区间赋值。所以我们对每个标记需要开线段树来维护更改的位置

    attack
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • 51Nod--1001 数组中和等于K的数对

    题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1001

    指点
  • 蓝桥杯-2017年省赛C++B组题6-最大公共子串

    比如:”abcdkkk” 和 “baabcdadabc“, 可以找到的最长的公共子串是”abcd“,所以最大公共子串长度为4。

    Debug客栈
  • 栈缓冲区溢出

    https://baike.baidu.com/item/%E8%8E%AB%E9%87%8C%E6%96%AF%E8%A0%95%E8%99%AB/90359...

    字节脉搏实验室
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • 洛谷P3437 [POI2006]TET-Tetris 3D(二维线段树 标记永久化)

    对于这题来说,因为有修改操作,我们需要在外层线段树上也打标记,而且标记的形式是对一段区间赋值。所以我们对每个标记需要开线段树来维护更改的位置

    attack
  • 2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】

    Function Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券