[LeetCode] 310. Minimum Height Trees

🔦 質問リンク
🔊 파이썬 알고리즘 인터뷰冊の本を参考にしました.

題

ルートノードとしてツリー内のすべてのノードを選択できます.ルートを選択して最低高さに戻ります.
▼▼▼▼草
これはいくつかの考えを変える必要がある問題です.
ルートノードを選択して最小高さを求めるのではなく、リーフノードから削除を開始する場合は、残りのノードからルートノードを求めることができます.

無方向図なので、ディクシャナにはすべての側面映像が保存されています.

すべてのディック郡を迂回し、幹線が1本しかないノードを見つけてリストに追加します.(リーフノード)

で見つかったリーフノードをディレクトリから削除し、方向性がなく、別のノードでも削除します.

削除を行う他端ノードの幹線数が1であれば、そのノードは再びリーフノードとなる.

ノード全体の個数が2以下であることを繰り返し,残りのリーフノードがルートノードとなる.

🛠 コード#コード#

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n <= 1:
            return [0]

        # 양방향 그래프 구성
        graph = collections.defaultdict(list)
        for i, j in edges:
            graph[i].append(j)
            graph[j].append(i)

        # 첫 번째 리프 노드 추가
        leaves = []
        for i in range(n + 1):
            if len(graph[i]) == 1:
                leaves.append(i)

        # 루트 노드만 남을 때까지 반복 제거
        while n > 2:  # 2개 남았을 땐 서로가 리프노드가 되므로 반복문을 빠져나온다.
            n -= len(leaves)
            new_leaves = []
            for leaf in leaves:
                neighbor = graph[leaf].pop()  # 1개 연결되있던 노드를 빼서 다음 조건 노드로 선택한다.
                graph[neighbor].remove(leaf)  # 일단 리프노드를 제외시킨다.

                if len(graph[neighbor]) == 1:  # 다음 조건 노드의 값의 갯수가 1인지(리프노드) 검사한다.
                    new_leaves.append(neighbor)

            leaves = new_leaves

        return leaves

📝 整理する
繰り返しが2より大きいのは,2つのノードが残っている場合は互いにリーフノードであり,続けている場合はルートノードを得ることができないためである.また,ノードが1つ残っている場合には,リーフノードがなくなり,それ自体がルートノードとなり,そのまま戻ればよい.
🎈 リファレンス
ブックリンク