CODE[VS] 1501 二叉树最大宽度和高度

题目描述 Description

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

输入描述 Input Description

第一行一个整数n。

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

输出描述 Output Description

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

样例输入 Sample Input

2 3

4 5

0 0

样例输出 Sample Output

2 3

数据范围及提示 Data Size & Hint

n<16

默认第一个是根节点

以输入的次序为编号

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

注意：第二题有极端数据！

0 0

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

看看这个：https://www.cnblogs.com/shenben/p/5516842.html

然后理解一下宽度的意思，深度比较好理解了。

二叉树的宽度是指具有节点数最多的那一层的结点个数。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring> 
 6 using namespace std;
 7 
 8 int a[30][3],b[30];
 9 int n,x,y,k,wide,deep;
10 
11 int main()
12 {
13     scanf("%d",&n);
14     for(int i=1; i<=n; i++)
15     {
16         scanf("%d%d",&x,&y);
17         a[i][0]=x;
18         a[i][1]=y;
19         a[x][2]=i;
20         a[y][2]=i;
21     }
22     for(int i=1; i<=n; i++)
23     {
24         k=1;
25         x=a[i][2];
26         while(x!=0)
27         {
28             k++;
29             x=a[x][2];
30         }
31         b[k]++;
32         if(k>deep) deep=k;
33         if(b[k]>wide) wide=b[k];
34     }
35     printf("%d %d
",wide,deep);
36     return 0;
37 }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 #include<cstring>
 6 using namespace std;
 7 
 8 int n,ans1,ans2;
 9 int fa[1002],deep[1002],wide[1002];
10 
11 struct node
12 {
13     int l,r;
14 } a[1002];
15 
16 void dfs(int now)
17 {
18     deep[now]=deep[fa[now]]+1;
19     ans2=max(ans2,deep[now]);
20     wide[deep[now]]++;
21     if(a[now].l ) 
22         dfs(a[now].l );
23     if(a[now].r )
24         dfs(a[now].r );
25 }
26 
27 int main()
28 {
29     scanf("%d",&n);
30     fa[1]=0;
31     for(int i=1; i<=n; ++i)
32     {
33         scanf("%d%d",&a[i].l ,&a[i].r );
34         fa[a[i].l ]=i;
35         fa[a[i].r ]=i;
36     }
37     dfs(1);
38     for(int i=1; i<=n; ++i)
39         ans1=max(ans1,wide[i]);
40     printf("%d %d",ans1,ans2);
41 }