2263번: 트리의 순회
첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
www.acmicpc.net
아이디어:
이진트리 / 입력의 첫줄은 inorder = 중위순회, 둘째줄은 postorder = 후위순회.. -> 전위순회 구하기.
중위순회(LVR)
후위순회(LRV) -> 맨 마지막 원소가 루트.
전위순회(VLR) -> 후위순회에서 중위순회를 사용하여 루트를 순서대로 뽑아내면 된다.
중위순회는 루트를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나누어지므로, 후위순회[-1](루트)를 중위순회에서 찾고그 인덱스-1까지를 후위순회에서 잘라서 다시 반복한다..
왼쪽 서브트리에서 모두 출력하면 오른쪽 서브트리도 똑같이 반복한다.
solve(instart, div-1, poststart, poststart+left-1)
여기서 왜 poststart+left-1을 하는지가 이해가 안됐었다. 나는 div-1이라고 생각했기 때문이다. 그런데, 루트를 기준으로 왼쪽 서브트리를 탐색할때는 저 방법이 상관 없지만 오른쪽 트리를 탐색하는 경우에는 div-1로 하면 인덱스가 맞질 않는다.
그리고 div를 구할때 index함수를 이용했더니 시간초과가 나와서 시간을 단축하기 위해 인덱스 배열을 따로 만들었더니 통과했다.
#2263 트리의 순회
import sys
sys.setrecursionlimit(10**9)
n = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))
postorder = list(map(int, sys.stdin.readline().split()))
index = [0]*(n+1)
for i in range (n):
index[inorder[i]] = i #root위치 찾는 걸 빠르게 하기 위해서
def solve(instart, inend, poststart, postend):
if (instart>inend or poststart>postend): return
root = postorder[postend]
print(root, end=" ")
#div = inorder.index(root) #중위순회에서 root의 위치
div = index[root]
left = div - instart #중위순회의 시작인덱스부터 div까지의 거리
solve(instart, div-1, poststart, poststart+left-1) #왼쪽 서브트리
solve(div+1, inend, poststart+left, postend-1) #오른쪽 서브트리
solve(0,n-1,0,n-1)
'알고리즘💻 > 트리' 카테고리의 다른 글
BOJ 4256번: 트리 (0) | 2021.02.09 |
---|---|
BOJ 1967번: 트리의 지름 (0) | 2021.02.08 |
BOJ 5639번: 이진 검색 트리 (0) | 2021.02.08 |
BOJ 1991번: 트리 순회 (0) | 2021.02.08 |
BOJ 11725번: 트리의 부모 찾기 (0) | 2021.02.08 |