9934_완전 이진 트리 (Python)
0. 출처
1. 기록
2. 풀이
(1) 아이디어, 시간복잡도, 자료구조
1. 아이디어
>> 문제에서 주어진 방문순서는 중위 순회이다.
>> 레벨과 방문순서가 주어진다.
>> 주어진 것으로 트리의 정보를 구해야 한다.
>> 어떻게 구하지..?
>> 중위순회를 반대로 실행해야 한다.
>> level 활용하기
>> 중위순회 입력된 리스트 가운데가 항상 root 노드임을 활용하기
>> 중위 순회로 입력된 리스트를 왼쪽 부분 트리, 오른쪽 부분 트리로 쪼갤 줄 알아야한다.
2. 시간복잡도
>>
3. 자료구조
>>
(2) 예제 입력, 예제 출력
- 예제 입력 1 -
2
2 1 3
- 예제 출력 1 -
1
2 3
- 예제 입력 2 -
3
1 6 4 3 5 2 7
- 예제 출력 2 -
3
6 2
1 4 5 7
(3) 코드
k = int(input())
inorder = list(map(int, input().split()))
answer = [[] for _ in range(k)]
def dfs(inorder, depth):
# 트리의 root index를 찾아낸다.
mid = (len(inorder) // 2)
# 해당 깊이에 해당하는 node를 추가한다.
answer[depth].append(inorder[mid])
if len(inorder) == 1:
return
dfs(inorder[:mid], depth+1)
dfs(inorder[mid+1:], depth+1)
dfs(inorder, 0)
for i in answer:
print(*i)
(4) 정리
(5) 참고
참고 풀이