이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다.
이와 같은 규칙에 따라 이진트리를 그릴 때 각 레벨의 너비는 그 레벨에 할당된 노드 중 가장 오른쪽에 위치한 노드의 열 번호에서 가장 왼쪽에 위치한 노드의 열 번호를 뺀 값 더하기 1로 정의한다. 트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다.
아래 그림은 어떤 이진트리를 위의 규칙에 따라 그려 본 것이다. 첫 번째 레벨의 너비는 1, 두 번째 레벨의 너비는 13, 3번째, 4번째 레벨의 너비는 각각 18이고, 5번째 레벨의 너비는 13이며, 그리고 6번째 레벨의 너비는 12이다.
우리는 주어진 이진트리를 위의 규칙에 따라 그릴 때에 너비가 가장 넓은 레벨과 그 레벨의 너비를 계산하려고 한다. 위의 그림의 예에서 너비가 가장 넓은 레벨은 3번째와 4번째로 그 너비는 18이다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때는 번호가 작은 레벨을 답으로 한다. 그러므로 이 예에 대한 답은 레벨은 3이고, 너비는 18이다.
임의의 이진트리가 입력으로 주어질 때 너비가 가장 넓은 레벨과 그 레벨의 너비를 출력하는 프로그램을 작성하시오
첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. 노드들의 번호는 1부터 N까지이며, 자식이 없는 경우에는 자식 노드의 번호에 -1이 주어진다.
첫째 줄에 너비가 가장 넓은 레벨과 그 레벨의 너비를 순서대로 출력한다. 너비가 가장 넓은 레벨이 두 개 이상 있을 때에는 번호가 작은 레벨을 출력한다.
import java.util.*;
import java.io.*;
public class Main {
static int N, idx=1, level=1;
static int[] min, max;
static List<Node> tree = new ArrayList<>();
public static void main (String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
min = new int[N+1];
Arrays.fill(min, N);
max = new int[N+1];
for (int i = 0; i <= N; i++) {
tree.add(new Node(i, -1, -1));
}
// 노드 세팅.
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int val = Integer.parseInt(st.nextToken());
int left = Integer.parseInt(st.nextToken());
int right = Integer.parseInt(st.nextToken());
tree.get(val).left = left;
tree.get(val).right = right;
if (left != -1)
tree.get(left).parent = val;
if(right != -1)
tree.get(right).parent = val;
}
int root = 0;
for (int i = 1; i <= N; i++)
if (tree.get(i).parent == -1)
root = i;
// 중위 순회.
inOrder(root, 1);
int result = max[1]-min[1]+1;
int resultIdx = 1;
for (int i = 2; i <= level; i++) {
int num = max[i] - min[i]+1;
if (result < num) {
result = num;
resultIdx = i;
}
}
System.out.println(resultIdx + " " + result);
}
public static void inOrder(int rootIdx, int lv) {
Node root = tree.get(rootIdx);
if (level < lv)
level = lv;
if (root.left != -1) {
inOrder(root.left, lv+1);
}
min[lv] = Math.min(min[lv], idx);
max[lv] = idx;
idx++;
if (root.right != -1)
inOrder(root.right, lv+1);
}
}
class Node {
int val, left, right, parent;
Node (int val, int left, int right) {
this.parent = -1;
this.val = val;
this.left = left;
this.right = right;
}
}