- 时间限制: 1 s
- 空间限制: 128000 KB
- 题目等级: 白银 Silver
点此跳转
【题目描述】
给出一个二叉树，输出它的最大宽度和高度。
【输入描述】
第一行一个整数n。
下面n行每行有两个数，对于第i行的两个数，代表编号为i的节点所连接的两个左右儿子的编号。如果没有某个儿子为空，则为0。
【输出描述】
输出共一行，输出二叉树的最大宽度和高度，用一个空格隔开。
【样例输入】
5
2 3
4 5
0 0
0 0
0 0
【样例输出】
2 3
【数据范围及提示】
n<16默认第一个是根节点
代码实现：
/*
作者：Zforw
题目：p1501二叉树最大宽度和高度
*/
＃include< cstdio >
＃include< iostream>
using namespace std;
int l[30],r[30],fa[30],b[30],n,k,width,depth ;
int main（）{
cin>>n;
for（int i = 1 ; i <= n; i ++
{
cin>>l[i]>>r[i]; //储存左右孩子
fa[l[i]]=fa[r[i]]=i;; //储存其父节点
}
for（int i = 1 ; i <= n; i ++）{
k = 1 ;
x = fa[i];
while（x！= 0）{
k++;
x = fa[x];
}
//从下向上找，一直找到根节点，k为深度
//b[k]保存深度为k的节点的个数
b[k]++;
depth=max(depth,k);
width=max(width,b[k]);
}
cout<<width<<" "<<depth;
return 0 ;
}