[BJ] 2250. 트리의 높이와 너비.java

2250번: 트리의 높이와 너비

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Node {

	int number;
	int leftCount;
	int rightCount;

	Node left;
	Node right;
	Node parent;

	public Node() {
		this.leftCount = 0;
		this.rightCount = 0;

		this.parent = null;
		this.right = null;
		this.left = null;
	}

}

class Tree {

	int rowMax = 1;

	int N;

	int[][] differ;

	public Tree(int N) {
		this.N = N;

		differ = new int[N + 1][2];

		for (int i = 1; i < N + 1; i++) {
			differ[i][0] = Integer.MAX_VALUE;
			differ[i][1] = Integer.MIN_VALUE;
		}
	}

	public Node findRoot(Node node) {
		while (node.parent != null) {
			node = node.parent;
		}
		return node;
	}

	public void preOrder(int row, int col, Node node, boolean[][] visited) {
		rowMax = Math.max(rowMax, row);

		differ[row][0] = Math.min(differ[row][0], col);
		differ[row][1] = Math.max(differ[row][1], col);

		if (node != null) {
			int term;
			if (node.left != null) {
				term = node.left.rightCount;
				visited[row + 1][col - term - 1] = true;
				preOrder(row + 1, col - term - 1, node.left, visited);

			}

			if (node.right != null) {
				term = node.right.leftCount;
				visited[row + 1][col + term + 1] = true;
				preOrder(row + 1, col + term + 1, node.right, visited);

			}

		}
	}

	public void postOrder(Node node) {

		Node lc, rc;
		if (node != null) {
			lc = node.left;
			rc = node.right;
			postOrder(lc);
			postOrder(rc);

			if (lc != null) {
				node.leftCount = lc.leftCount + lc.rightCount + 1;
			}

			if (rc != null) {
				node.rightCount = rc.leftCount + rc.rightCount + 1;
			}
		}
	}
}

public class Main {

	public static int N;

	public static Node[] nodes;

	public static boolean[][] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str;

		N = Integer.parseInt(br.readLine());

		nodes = new Node[N + 1];

		visited = new boolean[N + 1][N + 1];

		for (int i = 0; i < N + 1; i++) {
			nodes[i] = new Node();
		}

		int v, l, r;
		Node endNode = new Node();
		for (int i = 0; i < N; i++) {
			str = br.readLine().split(" ");
			v = Integer.parseInt(str[0]);
			l = Integer.parseInt(str[1]);
			r = Integer.parseInt(str[2]);

			nodes[v].number = v;

			if (l != -1) {
				nodes[v].left = nodes[l];
				nodes[l].parent = nodes[v];
			}

			if (r != -1) {
				nodes[v].right = nodes[r];
				nodes[r].parent = nodes[v];
			}

			if (l == -1 && r == -1) // 리프노드 한 개를 찾는다.
				endNode = nodes[v];

		}
		
		// 트리를 생성함
		Tree tc = new Tree(N);

		// 루트 노드를 찾기
		Node root = tc.findRoot(endNode);

		tc.postOrder(root); // root 노드를 기준으로 후위순회를 한다.

		visited[root.number][nodes[root.number].leftCount + 1] = true;

		tc.preOrder(1, root.leftCount + 1, root, visited); // int row, int col, Node node, boolean[][] visited

		int resultNum = 1, resultMax = 1; // 루트 노드만 존재하는 경우가 초기값이다.

		int term;
		for (int i = 2; i < tc.rowMax + 1; i++) {
			term = tc.differ[i][1] - tc.differ[i][0] + 1;
			if (term > resultMax) {
				resultNum = i;
				resultMax = term;
			}
		}

		System.out.println(resultNum + " " + resultMax);

	}

}

---

📌 트리의 높이와 너비에 대한 설명

1. 2차원 배열에서 왼쪽 자식 노드의 위치는 왼쪽 자식 노드의 오른쪽 자식 노드의 수를 보면 알 수 있다. (오른쪽 자식 노드는 오른쪽 자식 노드의 왼쪽 자식 노드의 수를 보면 알 수 있다)

2. 각 노드에서 왼쪽과 오른쪽의 자식 노드 수는 후위 순회를 통해 구한다.

3. 2차원 배열에서 노드가 생길 2차원 좌표는 전위 순회를 통해 구한다.