[파이썬]백준 9934 완전이진트리

링크

백준 9934 완전이진트리

inorder 순회를 반대로 하면되는데.. 처음엔 어떻게 할까 고민하면서 입출력 데이터를 보다보니 방법이 보였다.

순회한 순서에서 가장 가운데의 수가 트리의 루트가 되며
해당 수를 기준으로 좌우로 나눴을 때 다시 가운데의 수가 서브 트리의 루트가 된다.

분할정복을 하는 것처럼 계속 가운데 수를 찾고 왼쪽 오른쪽으로 잘라나가며 풀었다.

정답 코드

def sol(start, end , level):
    if start == end:
        ans[level].append(tree[start])
        return
    center = (start + end) // 2
    ans[level].append(tree[center])
    sol(start, center - 1, level + 1)
    sol(center + 1, end, level + 1)


Level = int(input())
tree = list(map(int, input().split()))
l = len(tree)
ans = [[] for _ in range(Level)]

sol(0, l - 1, 0)
for a in ans:
    print(*a)

알게된 것👨‍💻

• 순회의 결과를 보고 트리를 만들기!