Poj 3246 Balanced Lineup（线段树基础） - c++编程基础

题目描述 Description

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

输入描述 Input Description

第一行一个整数n。

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

输出描述 Output Description

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

样例输入 Sample Input

2 3

4 5

0 0

样例输出 Sample Output

2 3

#include   
#include   
#include   
#include   
#include   
#include   
#include   
  
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 ;  
}  

#include
#include
#include
#include
#include
#include
#include

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 ;
}