트리의 지름

트리의 지름은 트리의 노드들 중 가장 먼 거리를 가지는 두 노드 사이의 거리를 의미합니다.

 

---

알고리즘

 

1. 임의의 노드 x를 선택한다.

2. dfs로 x와 가장 먼 노드(A)를 구한다. 만약 가장 먼 노드가 2개 이상이라면 이들 중 어떠한 것을 선택해도 상관없다.

3. dfs를 한 번 더 돌려서, 노드 A로부터 가장 먼 노드(B)를 구한다. 

4. 노드 A와 노드 B의 거리가 트리의 지름이 된다.

 

노드 사이의 거리인데 최단거리 알고리즘을 돌려야하지 않나?! 싶기도 하지만 "트리"의 지름을 구하고 있음을 유의해봅시다.

트리의 성질 중 "트리의 두 노드 사이의 경로는 하나만 존재한다."가 있습니다. 

따라서 dfs 탐색 중에 구해지는 노드 사이의 거리가 최단거리가 됩니다.

---

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