10116 트리의 높이와 너비 Gold II

문제

이진 트리가 주어졌을 때, 각 레벨의 너비(가장 왼쪽 노드와 가장 오른쪽 노드 사이 거리 + 1) 중 최댓값과 그 레벨을 구하시오.

중위 순회 순서로 열 번호를 부여한다.

입력

첫째 줄에 노드 수 N (1 ≤ N ≤ 10,000)이 주어진다. 다음 N줄에 노드 번호, 왼쪽 자식, 오른쪽 자식이 주어진다. (-1이면 자식 없음)

출력

최대 너비를 가진 레벨과 너비를 공백으로 구분하여 출력한다.

19
1 2 3
2 4 5
3 6 7
4 8 -1
5 9 10
6 11 12
7 13 -1
8 -1 -1
9 14 15
10 -1 -1
11 16 -1
12 -1 -1
13 17 -1
14 -1 -1
15 18 -1
16 -1 -1
17 -1 19
18 -1 -1
19 -1 -1

3 18