题目描述 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 ;
}
给出一个二叉树,输出它的最大宽度和高度。
第一行一个整数n。
下面n行每行有两个数,是这个二叉树连接到的节点的编号,如果没有连接到节点,则为0。
输出共一行,输出二叉树的最大宽度和高度,用一个空格隔开。
5
2 3
4 5
0 0
0 0
0 0
2 3
#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 ;
}