时间限制: 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
这题你们别想投机取巧了,给我老老实实搜索!
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 }