[백준 2263번] 트리의 순회 (python)

문제

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

 

기록

(트리 5일차) 시간초과는 진짜 언제봐도 적응이 안된다. 아무리봐도 시간 줄일데가 없다고 생각했는데!! 그전에 비슷한 문제 풀어서 진짜 똑같이 풀었는데 시간초과나서 당황했다. 찾아보니까 inorder배열에서 root 인덱스 찾아내는 부분이 문제였다. 그래서 처음에 인덱스 미리 저장해놓고 바로바로 인덱스 찾을 수 있도록 변경했다.

 

내가 생각한 키포인트는 입력으로 주어진 inorder, postorder에서 각 순서의 특징을 이용하여 왼쪽/오른쪽/루트 분리하여 postorder순서로 출력될 수 있게 하는 것! 시간초과가 나면 재귀돌면서 inorder배열에서 그때그때 root index 찾지말고, 처음에 인덱스 저장해놓고 바로 찾을 수 있도록 구현하는 것!!

코드

from sys import stdin, setrecursionlimit
setrecursionlimit(10**9)

def print_pre(inidx, inlist, istart, iend, postlist, pstart, pend):

    # Base case
    if iend-istart <1 : return

    # Step
    # 1. inorder리스트의 루트인덱스 찾기, postorder 리스트의 중간인덱스 찾기
    root = postlist[pend-1]
    iroot = inidx[root]
    pmid = pstart + (iroot-istart)

    # 2. 루트-왼쪽노드-오른쪽노드 순으로 출력
    print(root, end=" ")
    print_pre(inidx, inlist, istart, iroot, postlist, pstart, pmid)
    print_pre(inidx, inlist, iroot+1, iend, postlist, pmid, pend-1)
    return


# 변수 초기화
n = int(stdin.readline())
inlist = list(map(int, stdin.readline().split()))
postlist = list(map(int, stdin.readline().split()))
inidx = [0]*1000001
for i, node in enumerate(inlist):
    inidx[node] = i

# 함수 호출
print_pre(inidx, inlist, 0, len(inlist), postlist, 0, len(postlist))

1. 변수 초기화

입력으로 들어온 값 변수에 저장하고, 노드 입력하면 바로 inorder 배열의 인덱스 접근할 수 있도록 배열 만들었다.

 

2. preorder 순회하면서 노드 출력

print_pre 함수는 입력된 배열값을 preorder순서로 바꿔 출력하는 재귀함수다. postorder배열은 왼쪽-오른쪽-루트 순서로 마지막값이 루트노드니까 찾아서 저장하고 -> inorder은 왼쪽-루트-오른쪽 순서니까 루트기준으로 나눠서 왼쪽/오른쪽 분리하고 -> postorder배열에서도 앞에서 찾은 양쪽서브트리 개수 이용하여 왼쪽/오른쪽 서브트리 분리한다. 그리고 preorder 순서로 노드 출력될 수 있게 구현!