티스토리 뷰
Study/Baekjoon
[Python] 백준 5639번 이진 검색 트리, 2263번 트리의 순회 | 트리 순회 변환 - 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)
yeorii 2024. 5. 28. 13:49
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
n = int(input())
inorder = list(map(int, input().split())) # left > root > right
postorder = list(map(int, input().split())) # left > right > root
inorder_idx = [0] * (n+1)
for idx, i in enumerate(inorder):
inorder_idx[i] = idx
def preorder(inorder_l, inorder_r, postorder_l, postorder_r):
if postorder_l > postorder_r:
return
root = postorder[postorder_r]
print(root, end=' ')
root_idx = inorder_idx[root]
len_l = root_idx - inorder_l
len_r = inorder_r - root_idx
preorder(inorder_l, root_idx-1, postorder_l, postorder_l+len_l-1)
preorder(root_idx+1, inorder_r, postorder_r-len_r, postorder_r-1)
preorder(0, n-1, 0, n-1)
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
n = int(input())
inorder = list(map(int, input().split())) # left > root > right
postorder = list(map(int, input().split())) # left > right > root
inorder_idx = [0] * (n+1)
for idx, i in enumerate(inorder):
inorder_idx[i] = idx
def preorder(inorder_l, inorder_r, postorder_l, postorder_r):
if postorder_l > postorder_r:
return
root = postorder[postorder_r]
print(root, end=' ')
root_idx = inorder_idx[root]
len_l = root_idx - inorder_l
len_r = inorder_r - root_idx
preorder(inorder_l, root_idx-1, postorder_l, postorder_l+len_l-1)
preorder(root_idx+1, inorder_r, postorder_r-len_r, postorder_r-1)
preorder(0, n-1, 0, n-1)'Study > Baekjoon' 카테고리의 다른 글
| [Python] 백준 30804번 과일 탕후루 | 투포인터, 브루트포스 알고리즘 (5) | 2024.06.13 |
|---|---|
| [Python] 백준 11000번 강의실 배정, 1931번 회의실 배정 | 우선순위 큐 - 배정 (0) | 2024.05.30 |
| [Python] 백준 1629번 곱셈, 13171 A | 분할 정복을 이용한 거듭제곱 (0) | 2024.05.24 |
| [Python] 백준 7785번 회사에 있는 사람 | set() (1) | 2024.02.12 |
| [Python] 백준 1009번 분산처리 | 런타임에러(KeyError) (0) | 2023.08.05 |