항해99 - 3주차, 최소 높이 트리

Jang Seok Woo·2022년 1월 30일

BFS DFS 이진트리

알고리즘

목록 보기

40/74

Today I learned
2022/01/26

회고록

1/26

항해 99, 알고리즘 2주차

교재 : 파이썬 알고리즘 인터뷰

이진트리

1. 이론

이진 트리(binary tree)의 정의

트리 중에서 가장 많이 쓰이는 트리가 이진트리이다. 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree) 라고 한다. 서브트리는 공집합일 수 있다. 따라서 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하가 된다. (차수(degree)는 어떤 노드가 가지고 있는 자식 노드의 개수)

이진트리

공집합이거나
루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진트리의 서브트리들은 모두 이진트리여야 한다.

이진트리의 성질

n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선을 가진다. 그 이유는 이진트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모노드를 가진다. 그리고 부모와 자식 간에는 정확하게 하나의 간선만이 존재한다.
높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2의h제곱 -1개의 노드를 가진다.

2. 문제

A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

링크텍스트

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

https://leetcode.com/problems/minimum-height-trees/

3. MySol

BinaryTree, DFS

#binary BFS Templates
import collections
from collections import deque

from binary.prac import make_tree_by


def solution(n, edges):

    graph = collections.defaultdict(list)

    for i,j in edges:
        graph[i].append(j)
        graph[j].append(i)

    print(f'{graph}')

    leaf = []

    for i in range(n+1):
        if len(graph[i]) == 1:
            leaf.append(i)

    while n>2:
        n -= len(leaf)
        temp_leaf = []

        for i in leaf:
            temp=graph[i].pop()
            graph[temp].remove(i)

            if(len(graph[temp])==1):
                    temp_leaf.append(temp)

        leaf = temp_leaf

    return leaf

if __name__ == '__main__':

    n =6

    edges = [[0,3],[1,3],[2,3],[4,3],[5,4]]

    result = solution(n, edges)

    print(f'{result}')