9934: 완전한 이진 트리
정규 직원은 슬로베니아 Donji Andrijevci 마을을 여행합니다. 도시의 거리는 깊이 K의 완전한 이진 트리를 형성합니다. 깊이 K의 완전한 이진 트리에는 총 2K-1개의 노드가 있습니다. (아래에
www.acmicpc.net
(문제)
(암호)
#중위 순회 문제
#순서가 주어지고 트리를 유추하는 문제
import sys
input = sys.stdin.readline
k = int(input())
squence = list(map(int, input().split()))
trees = (() for _ in range(k))
#완전 이진 트리이니까 각 층의 노드는 중간의 값
def binary_tree(array, depth):
mid_index = len(array) // 2
trees(depth).append(array(mid_index))
#만약 input_array가 길이가 1이라면 해당 재귀 종료
if len(array) == 1:
return
#왼쪽 노드부터 먼저 추가 되어야 하니까
binary_tree(array(:mid_index), depth + 1)
binary_tree(array(mid_index+1:), depth + 1)
#재귀 함수 0 층부터 실행
binary_tree(squence, 0)
for tree in trees:
print(*tree)
(논평)
이것은 우리가 어제 풀었던 이진 트리 검색 문제의 변형입니다.
어제의 문제의 경우 정답으로 검색순서를 찾는 것이 트리와 목적이었기에,
이 문제에는 검색 순서가 지정되고 트리가 추론됩니다.
문제의 핵심은 두 가지로 요약할 수 있습니다.
하나. 순서 순회 트리 – 문제의 조건은 순회입니다.
2. 완전한 이진 트리 트리의 모양은 완전한 이진 트리로서 왼쪽 노드가 하나만 있는 경우는 없고 왼쪽 노드가 있는 곳에 오른쪽 노드도 있는 경우가 없다.
이 두 가지 핵심 사항을 기반으로 문제에 대한 솔루션을 쉽게 정의할 수 있습니다.
주어진 순서대로 중앙값은 첫 번째 노드입니다.될거야
즉, 예제 2를 예로 들면,
기입:
3
1 6 4 3 5 2 7따라서 여기서 첫 번째 노드의 값은 3입니다.
그리고 왼쪽의 두 번째 수준 노드는 중앙값 바로 앞의 값으로 인덱스된 배열의 중앙값이 됩니다.
두 번째 수준의 오른쪽에 있는 노드는 중앙값 이후의 값에서 마지막 값까지 인덱싱된 배열의 중앙값이 됩니다.
숫자로 보면 쉽다
1층 – 1 6 4 삼 5 2 7
2층(왼쪽): 1층 6 4, 2층(오): 5 2 7
3층(왼쪽 왼쪽): 하나3층(좌우): 43층(오른쪽 왼쪽): 53층(오): 7
따라서 정답은
3
6 2
1 4 5 7~이다
이것을 논리로 정리하면 다음과 같습니다.
def function(input배열, 층):
중앙값 계산
배열의 중앙값에 해당하는 값을 해당 층에 추가
그리고 만약 배열의 길이가 1이라면 재귀 종료
왼쪽 : function(재귀 중앙값 이전까지 인덱싱한 배열, 층+1)
오른쪽 : function(재귀 중앙값 이후부터 인덱싱한 배열, 층+1)
코드에서 직접 구현해 보겠습니다.
#중위 순회 문제
#순서가 주어지고 트리를 유추하는 문제
import sys
input = sys.stdin.readline
k = int(input())
squence = list(map(int, input().split()))
trees = (() for _ in range(k))먼저 트리의 레이어를 k-변수로 입력하고,
검색 순서를 목록으로 저장
그리고 최대 k -> ex) k==3 , trees = ( ( ), ( ), ( ) ) 의 중복 목록을 생성합니다.
#완전 이진 트리이니까 각 층의 노드는 중간의 값
def binary_tree(array, depth):
mid_index = len(array) // 2
trees(depth).append(array(mid_index))
#만약 input_array가 길이가 1이라면 해당 재귀 종료
if len(array) == 1:
return
#왼쪽 노드부터 먼저 추가 되어야 하니까
binary_tree(array(:mid_index), depth + 1)
binary_tree(array(mid_index+1:), depth + 1)그리고 재귀 함수를 사용할 것이기 때문에 위와 같이 함수를 정의해 봅시다.
함수의 입력은 현재 수준인 검색 시퀀스의 배열입니다.
이것이 함수 내에서 작동하는 방식입니다.
먼저 입력으로 제공된 배열의 중간 인덱스를 찾습니다. – 입력 배열의 길이를 2로 나눕니다.
그리고 앞에서 만든 트리의 레이어 위치에 중앙값을 추가합니다.
그런 다음 재귀 종료 규칙을 설정합니다. 입력 배열의 길이가 1이면 재귀가 종료됩니다.
그렇지 않은 경우 다음 재귀가 수행됩니다.
우리가 하고 있는 것은 중간 수준 순회이기 때문에
맨 아래 레이어 왼쪽 노드를 먼저 트리에 추가해야 합니다.
따라서 중앙값 앞의 값으로 인덱스된 배열을 입력으로 삽입하고 그 수준의 첫 번째 수준에 더한 수준을 입력으로 주어 재귀를 수행 – 왼쪽 자식 노드 추가
그런 다음 중앙값 이후의 값부터 indexed 배열을 입력으로 삽입하고 해당 레벨의 첫 번째 레벨이 입력으로 추가된 레벨을 입력하여 재귀 실행 – 오른쪽 자식 노드 추가
#재귀 함수 0 층부터 실행
binary_tree(squence, 0)
for tree in trees:
print(*tree)이렇게 생성된 재귀 함수가 레이어 0부터 시작하면 트리에 트리가 저장된다.
이후 첫 번째 레이어부터 for 문까지 순차적으로 출력하면 정답이 나옵니다.
