[백준 2250] 트리의 높이와 너비

https://www.acmicpc.net/problem/2250

2250번: 트리의 높이와 너비

요구사항

1. 각 층수의 너비 구하기

2. 중위 순회 구현

 

풀이

1. 트리의 루트를 구한다.

2. 루트로 부터 중위순회 시작(LVR)

3. 층 별 최대, 최소를 갱신해주면 중위순회

4. 최대값, 층수 출력

 

#include <stdio.h>
#include <map>
#include <algorithm>
//#include "Windows.h"
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
struct go {
	int left;
	int right;
};
struct go1 {
	ll floor;
	ll pos;
};

go node[10002];
go1 info[10002];
int visit[10002];
int root;
ll high[10002];
ll low[10002];
int n;
ll pos = 1;
ll maxlevel = 0;
void dfs(ll Node, ll level) {
	if (node[Node].left >0) {
		dfs(node[Node].left, level + 1);
		maxlevel = max(maxlevel, level + 1);
	}
	high[level] = max(high[level], pos);
	low[level] = min(low[level], pos);

	pos++;

	if (node[Node].right>0) {
		dfs(node[Node].right, level + 1);
		maxlevel = max(maxlevel, level + 1);
	}
}
int main()
{
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		high[i] = 0;
		low[i] = 987654321;
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		node[x].left = y;
		node[x].right = z;
		visit[x]++;
		if (y != -1) {
			visit[y]++;
		}
		if (z != -1) {
			visit[z]++;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (visit[i] == 1)
			root = i;
	}

	dfs(root, 1);
	ll tdist = 0;
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		int dist = high[i] - low[i] + 1;
		if (tdist<dist) {
			tdist = dist;
			ans = i;
		}
	}
	cout << ans << " " << tdist << endl;
}