백준 파이썬 2263 트리의 순회

https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
inorder = list(map(int,input().split()))
postorder = list(map(int,input().split()))
position = [0]*(n+1)
for i in range(n):
    position[inorder[i]] = i

def preorder(istart,iend,pstart,pend):
    if istart > iend or pstart > pend:
        return

    root = postorder[pend]
    print(root,end=' ')

    left_cnt = position[root] - istart
    right_cnt = iend - position[root]

    preorder(istart,position[root]-1,pstart,pstart+left_cnt-1)
    preorder(position[root]+1,iend,pend-right_cnt,pend-1)


preorder(0,n-1,0,n-1)

inorder(중위순회), postorder(후위순회)를 통해 preorder(전위순회)를 구할 수 있습니다.

 

1. postorder의 맨 마지막 정점은  preorder의 처음 정점입니다.

postorder는 (왼쪽자식)(오른쪽자식)(정점) 인 반면 preorder는 (정점)(왼쪽자식)(오른쪽자식) 이기 때문입니다.

 

2. postorder의 맨 마지막 정점을 이용해 inorder에서 왼쪽자식의 개수, 오른쪽자식의 개수를 알 수 있습니다.

inorder는 (왼쪽자식)(정점)(오른쪽자식) 이기 때문에 inorder에서의 정점의 인덱스를 알고 있으면 왼쪽자식의 개수, 오른쪽자식의 개수를 알 수 있습니다.

 

3. 왼쪽자식, 오른쪽자식으로 나눠 왼쪽자식 먼저 재귀를 돌면서 전위순회를 찾아냅니다.

 

 

https://ca.ramel.be/114 

백준 2263번: 트리의 순회 (Python)

참고한 블로그입니다.