2250 트리의 너비와 높이

트리의 너비는 순회를 이용해서 구했고, 높이는 순회하면서 depth 배열에 높이를 저장해서 구했다.

 

주의할 점은 루트 노드가 1이 아니다!

 

 

#include <iostream>
using namespace std;

struct node {int l, r,col;} arr[10010];

int a = 1,root;
int N, res1, res2;
int depth[10010];
bool isRoot[10010];

void search(int n, int lev){
    if(n == -1) return;
    depth[n] = lev;
    search(arr[n].l, lev + 1);
    arr[n].col = a++;
    search(arr[n].r,lev+1);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>N;
    for(int i = 1,c,v,b; i <= N; i++){
        cin>>c>>v>>b;
        arr[c].l = v;
        arr[c].r = b;
        isRoot[v] = true;
        isRoot[b] = true;
    }
    for(int i = 1; i<= N; i++){
        if(!isRoot[i]) {root = i; break;}
    }
    search(root,1);
    int level = 1;
    while(true){
        int mn = 10010, mx = 0;
        for(int i = 1; i <= N; i++){
            if(level == depth[i]){
                mn = min(mn,arr[i].col);
                mx = max(mx,arr[i].col);
            }
        }
        if(mx == 0) break;
        if(mx - mn + 1> res2){
            res2 = mx - mn+1;
            res1 = level;
        }
        level++;
    }
    cout<<res1<<" "<<res2;
    return 0;
}