[알고리즘][Python] 백준 2263 트리의 순회 문제 풀이

문제 출처 : www.acmicpc.net/problem/2263

2263번: 트리의 순회

---

문제 해석 : In-order, post-order가 주어지면 pre-order를 찾아 출력하는 문제이다.

 

문제 풀이 : 트리를 순회하기 위해서 일단 in-order를 통해서 idx를 만들어 주고 반복적으로 자신의 왼쪽 자식, 오른쪽 자식을 찾아서 만들어 주면 된다.

---

풀이 코드

import sys
sys.setrecursionlimit(10 ** 6)


def find_solution(l_in, r_in, l_post, r_post):

    if l_in > r_in or l_post > r_post:
        return

    parent = post_order[r_post]
    print(parent, end = " ")

    S_idx = idx[parent]
    left = S_idx - l_in

    find_solution(l_in, S_idx - 1, l_post, (l_post + left) - 1)
    find_solution(S_idx + 1, r_in, l_post + left, r_post - 1)


N = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))

idx = [0] * (N+1)
for i in range(N):
    idx[in_order[i]] = i

find_solution(0, N - 1, 0, N - 1)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.