[leetcode][310] Minimum Height Trees

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

 

---

N개의 노드가 있고 N-1개의 간선으로 연결된 무방향 그래프가 주어진다. 그래프는 순환 경로가 없고 모든 노드가 연결되어 있다.

노드들 중 루트 노드가 된다면 최소 높이를 가진 트리를 가질 수 있는 노드들을 구하라.

---

지난번에 푼 트리지름 관련 문제 참고.

임의의 지점 0 노드를 시작점으로 BFS를 한 번 돌려서 가장 멀리 있는 노드들을 가져온다.

이 노드들로 다시 한 번 BFS를 돌려서 가장 멀리있는 노드들을 가져오면 트리의 지름을 가지는 2개의 노드(let, a, b)를 알 수 있다

BFS를 만들면서 이전에 방문한 노드 번호를 저장하고 a -> b (트리 지름) 경로를 지날 때 방문하는 노드들을 임의의 배열에 저장한다.

경로 노드의 중간값(중위수)이 정답이 될 수 있는 경우이다. 만약 경로의 노드들의 수가 짝수라면 2개의 중간값을 가지고 둘 다 정답이 가능하다.

 

시간복잡도는 N-1개의 간선을 가지므로 O(N)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/310.%20Minimum%20Height%20Trees.cpp