백준 2263 트리의 순회 파이썬(python)

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

---

풀이

[알고리즘]

inorder와 postorder로 preorder를 유추하는 개념을 알고 있어야 풀 수 있는 문제이다. 개념을 이용한 분할 정복 알고리즘을 이용하여 해결 할 수 있다.

예시 트리

문제의 예시가 빈약해서 하나 예로 들어 살펴보자.

순회 순서

입력은 인 오더 : 1 2 4 9 5 3 7 8 6, 포스트 오더: 1 4 5 9 2 7 6 8 3

inorder는 left -> root -> right, postorder는 left-> right-> root 순서로 순회를 하게 된다. 

preorder 유추하기

postorder의 맨 끝은 root를 의미한다. 그 root 기준으로 inorder 순서에선 왼쪽, 오른쪽으로 서브 트리를 형성하게 된다.

계속해서 재귀로 들어가면서 root를 출력해주면 그것이 preorder 순서가 된다.

결과

[풀이 방법]

1. postorder에서 root 값을 찾은 뒤 inorder에서 해당 index를 계속해서 찾으면 시간이 소비된다.
2. 미리 inorder 값들의 index를 저장해놓을 필요가 있다.
3. 왼쪽 서브트리, 오른쪽 서브트리 index 값들을 저장하고 재귀를 이용해 풀어준다.
4. root, left, right 순서를 고려해 왼쪽 서브트리부터 들어간다.

import sys
sys.setrecursionlimit(10**9)
# inorder : left root right
# postorder : left right root
# preorder : root left right
# postorder 맨 끝은 root, inorder 그 root 왼쪽 오른쪽은 각각 서브 tree


N = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))
postorder = list(map(int, sys.stdin.readline().split()))

ix = [-1] * N
for i in range(N):
    ix[inorder[i]-1] = i


def preorder(ins, ine, pos, poe):
    if ins > ine or pos > poe:
        return
    root = postorder[poe]
    offset = ix[root-1] - ins
    print(root, end= " ")
    # 왼쪽 트리
    preorder(ins, ix[root-1]-1, pos, pos + offset-1)
    # 오른쪽 트리
    preorder(ix[root-1]+1, ine, pos+offset, poe-1)


preorder(0, N-1, 0, N-1)

 

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

2263번: 트리의 순회