310. Minimum Height Trees

문제 링크: https://leetcode.com/problems/minimum-height-trees/

Tree의 edge 리스트가 주어지면 그 edge들로 만들 수 있는 모든 minimum-height-trees (MHT)의 root를 출력 하는 문제이다.

우선 주어진 edge들로 tree를 만든다는 점에서 graph 문제와 유사하다. (Tree는 undirected graph)

그래프를 다루는 비슷한 문제로 Course Schedule이 있다.

Solution

1. Brute force

먼저, 문제의 요구사항을 따라가보면,

• 그래프의 각 노드를 tree를 만드는 root라고 가정한다.
  root node와 나머지 node들 간의 거리를 구한다. 최장거리가 이 tree의 height이 될 것이다.
• Minimun Height Tree의 정의에 따라, 최소 높이를 가진 tree를 골라낸다.

첫번째 step은 tree의 root에서부터 단말 노드까지의 최장 거리를 찾는 Maximum Depth of N-ary Tree 문제를 푸는 방법과 같다.
DFS나 BFS를 사용하면 된다.

효율성

시간복잡도는 O(N^2), (N은 트리의 노드 개수) 를 가지며 ~TLE~가 나온다.

2. 위상 정렬 (Topological Sort)