2250 트리의 높이와 너비

#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>
 
using namespace std;
 
vector<vector<int> > heightNd;
vector<pair<int, int> > child;
int par[10001] = { 0 };
int ndX[10001] = { 0 };
int maxWidth = -1 , mostLevel;
 
void levelWidth(int h) {
    for (int i = 1; i <= h; i++) {
        int levelL = 10001, levelR = -1;
        for (int j = 0; j < heightNd[i].size(); j++) {
            int idx = heightNd[i][j];
            int tmpX = ndX[idx];
 
            if (tmpX < levelL)
                levelL = tmpX;
            if (tmpX > levelR)
                levelR = tmpX;
        }
        int tmpWidth = levelR - levelL;
        if (maxWidth < tmpWidth) {
            maxWidth = tmpWidth;
            mostLevel = i;
        }
    }
}
 
int x = 1;
void traverse(int idx) {
    int l = child[idx].first;
    int r = child[idx].second;
 
    if (l != -1) 
        traverse(l);    
 
    ndX[idx] = x++;
 
    if (r != -1) 
        traverse(r);    
}
 
int findHeight(int root) {
    queue<pair<int, int> > q;
    q.push(make_pair(root, 1));
 
    int h, idx;
    while (!q.empty()) {
        idx = q.front().first;
        h = q.front().second;
        
        q.pop();
        heightNd[h].push_back(idx);
 
        int l = child[idx].first;
        int r = child[idx].second;
 
        if (l != -1)
            q.push(make_pair(l, h + 1));
        if (r != -1)
            q.push(make_pair(r, h + 1));
    }
    return h;
}
 
int main() {
    int n;
    scanf("%d", &n);
 
    child.resize(n + 2);
    heightNd.resize(n + 2);
 
    for (int i = 1; i <= n; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
 
        child[a].first = b;
        child[a].second = c;
        
        if (b != -1)
            par[b] = a;
        if (c != -1)
            par[c] = a;
    }
    //root 찾기
    int root = -1;
    for (int i = 1; i <= n; i++) 
        if (par[i] == 0) 
            root = i;
    //높이 찾기
    int height = findHeight(root);
    //순회하면서 좌표 갱신하기
    traverse(root);
    //각 레벨 당 최대 너비 찾기
    levelWidth(height);
 
    printf("%d %d", mostLevel, maxWidth + 1);
}

1. 중위순회를 통해 x 를 갱신한다

2. 각 레벨별로 최좌측, 최우측 x 좌표를 구한다

>> 이 두 가지를 떠올리는게 쉽지 않아서 다른 블로그를 참조했다

중요!!

아 그리고!

순회를 할때는 무조건 DFS를 사용해야 한다

BFS로는 절대 못품!