二叉树最大宽度和高度

时间:2022-04-15 17:31:54

题目描述 Description

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

输入描述 Input Description

第一行一个整数n。

下面n行每行有两个数,是这个二叉树连接到的节点的编号,如果没有连接到节点,则为0。

输出描述 Output Description

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

样例输入 Sample Input

5

2 3

4 5

0 0

0 0

0 0

样例输出 Sample Output

2 3

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<iomanip>

using namespace std;

int a[ 40 ][ 3 ] = { 0 } , num[ 40 ] ;

int w = 0 , d = 0 ;
void dfs( int x , int y )
{
num[ y ]++ ;
if( y > w )
w = y ;
if( a[ x ][ 1 ] != 0 )
dfs( a[ x ][ 1 ] , y + 1 ) ;
if( a[ x ][ 2 ] != 0 )
dfs( a[ x ][ 2 ] , y + 1 ) ;
}
int main()
{
int n ;
cin >> n ;
for( int i = 1 ; i <= n ; i++)
cin >> a[ i ][ 1 ] >> a[ i ][ 2 ] ;
dfs( 1 , 1 ) ;
for( int i = 1 ; i <= 16 ; ++i )
if( num[ i ] > d )
d = num[ i ] ;
cout << d << " " << w << endl ;
return 0 ;
}