항해99 - 3주차, 최소 높이 트리
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}')
4. 배운 점
- 이진트리에 대한 이해
- defaultdict를 이용
- 연결요소가 1개일 시 leaf 노드
- 마지막 2개 남기는 이유는 아직도 의문
5. 총평
이진트리, 리프노드 자르기 로직 연습
Author And Source
이 문제에 관하여(항해99 - 3주차, 최소 높이 트리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jsw4215/항해99-3주차-최소-높이-트리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)