2250. 트리의 높이와 너비

2250번: 트리의 높이와 너비

---

트리를 격자판에 그리려 한다. 격자판의 한 칸에는 노드 하나가 들어가며, 주어진 조건에 따라 그려야 한다.

 

가장 결정적인 조건은 3번 조건이다.

3. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.

이 조건을 활용하여 각 노드가 들어가야 할 칸을 결정할 수 있다.

 

어떤 노드가 위치할 수 있는 열의 범위를 [left, right]라고 하자. 노드의 왼쪽 자식은 노드보다 왼쪽에, 오른쪽 자식은 노드의 오른쪽에 위치해야 한다. 즉 노드의 왼쪽·오른쪽 자식의 수를 구하면 노드의 위치를 결정할 수 있다.

 

루트 노드는 [1, n] 범위에 위치할 수 있다. 루트에서 시작하여 왼쪽·오른쪽 자식의 개수를 각각 구하며 그래프를 순회하면 그림을 그릴 수 있다.

 

 

사실 이 문제에는 작지만 매운 함정이 있다. 우선 코드를 스스로 구현해 보고, 틀렸다면 아래의 글을 읽어 보자.

루트 노드가 1이 아닐 수 있다.

 

트리의 레벨은 가장 위쪽에 있는 루트 노드가 1이고 아래로 1씩 증가한다. 라는 문장 때문에 헷갈릴 수 있으나, 이 문장은 루트 노드의 레벨이 1이라는 의미이며 1번이 루트 노드라는 말이 아니다. 문장 자체가 좀 헷갈리긴 하다만..

 

어쨌든 그래서 우리는 루트 노드를 직접 찾아야 한다. 

루트 노드란 무엇인가? 부모가 없는 노드이다. 이 성질을 활용하면 어렵지 않게 루트를 구할 수 있을 것이다.

---

당분간은 트리 공부를 할 생각이다.