[백준 2263] 트리의 순회 python 파이썬

2263번 - 트리의 순회

문제 이해

이진 트리의 인오더(중위 순회)와 포스트오더(후위 순회)가 주어질 때,
프리오더(전위 순회)를 출력하면 되는 문제.

접근

아이디어

• 프리오더의 가장 오른쪽 값이 루트이다.
• 인오더에서 루트 값의 왼쪽값들은 왼쪽 서브트리, 오른쪽값들은 오른쪽 서브트리를 구성한다.

해당 아이디어를 기반으로 재귀적으로 해결해내면 된다.
처음엔 파이썬의 슬라이싱을 이용해 넘겨주는 방식으로 해결했는데, 그러한 방식은 메모리 초과가 나게 된다.
따라서 인덱스를 넘겨주는 방식으로 수정하였다.
재귀가 꽤나 깊이 들어가기 때문에 파이썬의 경우 sys.setrecursionlimit()을 통해 재귀의 깊이를 늘려주어야 한다.

정답 코드

import sys
input = sys.stdin.readline
def getInts(): return map(int, input().split())
sys.setrecursionlimit(int(1e5))


N = int(input())
_inorder = [*getInts()]
_postorder = [*getInts()]


def preorder(il, ir, pl, pr):
    if pr - pl >= 0:
        root = _postorder[pr]
        rootIdx = _inorder.index(root)
        print(root, end=" ")
        preorder(il, rootIdx-1, pl, pl+(rootIdx-il)-1)
        preorder(rootIdx+1, ir, pl+(rootIdx-il), pr-1)


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