220624 금 Algorithms TIL

리트코드 310. Minimum Height Trees Medium

• 문제
• 코드-파이썬

접근법 (책풀이, 파이썬 알고리즘 인터뷰)

• 이런 경우에서 최소 높이는 가장 가운데에 있는 값이고, 리프노드를 하나씩 제거하면서 남아 있는 값을 찾으면 가장 가운데에 있는 값이 마지막에 남게 된다.
• 책에서 알 수 있던 것은 결과가 최종으로 1개 아니면 2개가 나온다는 것이었다. 트리 구조 이기 때문에 3개가 있다고 했을 때 사이클이 만들어져야만 모두 동일한 간선을 가질 수 있는데 그건 트리라는 조건에 위배된다.
• 그래서 정답 코드에서는 한 개 혹은 두 개가 남을 때까지 계산했다.
• 나는 그를 모르고 풀어서 리프토느드로 센 개수와 현재 리프노드로 갱신된 노드(간선들이 다 지워져서)의 수의 합이 n일 때로 풀었다.
• private 있