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

문제 링크 : https://www.acmicpc.net/problem/9934

9934번: 완전 이진 트리

이진트리의 중위순회을 이용하여 풀었다.

중위 탐색은 왼쪽 자식노드 먼저 탐색하고 자신 노드 보고 오른쪽 자식 노드를 보는 순회 방식이다.

 

전위,중위,후위 순회 방식을 문제의 그림을 보고 설명하면 아래와 같다.

사진 링크 : https://www.acmicpc.net/problem/9934

 

전위 순회는 자신 노드를 먼저 확인하고 왼쪽 자식 노드를 탐색하고 오른쪽 자식 노드를 탐색하는 방식이다.

그림의 트리로 탐색한다면

3 6 1 4 2 5 7 순서로 탐색한다.

 

중위 순회는 왼쪽 자식 노드를 탐색하고 자신 노드를 확인 후 오른쪽 노드를 탐색하는 방식이다.

그림의 트리로 탐색한다면

1 6 4 3 5 2 7 순서로 탐색한다.

 

후위 순회는 왼쪽 자식 노드를 탐색하고 오른쪽 자식 노드를 탐색한 후 자신 노드를 확인하는 방식이다.

그림의 트리로 탐색한다면

1 4 6 5 7 2 3 순서로 탐색한다.

 

 

문제의 입력으로 주어진 상근이가 방문한 순서는 이진트리를 중위순회로 탐색한 것으로

자신 노드를 확인할 때 노드의 번호를 순서대로 저장한 것이다.

 

따라서 직접 중위순회로 탐색 하면서 자신 노드를 확인할 때 해당 깊이에 입력받은 번호를 차례대로 넣으면 된다.

 

from sys import stdin

input = stdin.readline

n = int(input())
nums = list(map(int, input().split()))
num_idx = 0
tree = [[] for _ in range(n)]
def solv():
    inorder(0)
    for row in tree:
        print(*row)
def inorder(depth):
    global tree,num_idx
    if depth == n:
        return

    inorder(depth+1)
    tree[depth].append(nums[num_idx])
    num_idx += 1
    inorder(depth+1)

solv()