ACM题目————二叉树最大宽度和高度

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

http://codevs.cn/problem/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

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

代码：

//树的DFS

#include <iostream>

#include <string.h>

using namespace std;

const int MAX = 1001 ;

int a[MAX][2], b[MAX] ;

int n, x, y ;//x--深度 y--宽度

void DFS(int i, int k)

{

    b[k] += 1;

    if( k>x ) x = k ;

    if(a[i][1]!=0) DFS(a[i][1], k+1);

    if(a[i][2]!=0) DFS(a[i][2], k+1);

}

int main()

{

    cin >> n ;

    memset(a,0,sizeof(a));

    memset(b,0,sizeof(b));

    for(int i=1; i<=n; i++)

        cin >> a[i][1] >> a[i][2] ;

    x = 0 ;

    DFS(1,1);

    for(int i=1; i<MAX; i++)

        if(b[i]>y) y=b[i] ;

    cout << y << " " << x << endl ;

    return 0;

}