[백준] 2263 트리의 순회 python

www.acmicpc.net/problem/2263

2263번: 트리의 순회

import sys; input = sys.stdin.readline
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
preorder = []
def order(inorder, postorder):
    if postorder == inorder:
        return reversed(postorder)
    ret = [postorder[-1]]
    ind = inorder.index(postorder[-1])
    ret += order(inorder[:ind],postorder[:ind])
    ret += order(inorder[ind+1:],postorder[ind:-1])
    return ret
print(*order(inorder, postorder))

처음시도했던 코드는 답은 잘 나오지만 슬라이싱을 사용하다보니 메모리가 초과했다.

 

import sys; input = sys.stdin.readline
sys.setrecursionlimit(100000)
n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))
ind = [0] * (n + 1)
for i in range(len(inorder)):
    ind[inorder[i]] = i

def order(ins=0, ine=n - 1, pos=0, poe=n - 1):
    if ins > ine or pos > poe:
        return
    print(postorder[poe], end=' ')
    # ind = inorder.index(postorder[poe])
    l = ind[postorder[poe]] - ins
    r = ine - ind[postorder[poe]]

    order(ins, ins + l - 1, pos, pos + l - 1)
    order(ine - r + 1, ine, poe - r, poe-1)
order()

인덱스로 접근해서 만들었느데 앞부분은 잘 되는데 뒷부분에서 접근이 잘 안되었다.

그래서 어찌어찌 찾아봤는데 조금만 더 생각했으면 풀수 있을뻔 했다...

 

크기를 찾아서 그만큼만 넣어주면 되는거였는데 참 아쉬운 문제다

 

---

항상 느끼지만 아직 많이 부족하다

참고한 블로그

bingorithm.tistory.com/5

"백준 2263번-트리의 순회" 반례 모음

fullmoon1344.tistory.com/116

[백준 2263] 트리의 순회 - Python (트리, 재귀)