[골드 4] 백준 5639 - 이진 검색 트리 (파이썬)
글 작성자: pental

https://www.acmicpc.net/problem/5639
풀이
전위 순회를 후위 순회로 변환하는 구현을 진행해야한다.
즉, 전위 순회 결과가 주어졌을 때, 해당 트리의 후위 순위 결과를 출력해야한다.
입력은 전위 순회 결과이며, 이진 검색 트리 조건이 적용된다.
- 왼쪽 자식 < 부모 < 오른쪽 자식
def postorder(start, end): if start >= end: return root = preorder[start] # 현재 서브트리의 루트 # 오른쪽 서브트리의 시작 인덱스를 찾기 right = start + 1 while right < end and preorder[right] < root: right += 1 # 왼쪽 서브트리 순회 postorder(start + 1, right) # 오른쪽 서브트리 순회 postorder(right, end) # 루트 출력 (후위 순회이므로 마지막에 출력) print(root)
preorder[start]는 항상 서브트리의 루트 노드이며, 그 다음부터 preorder[right] < root 이면 왼쪽 서브트리에 속한다.
조건이 깨지는 최초의 right는 오른쪽 서브트리의 시작점이며, 그 구간들을 기준으로 재귀적으로 분할하여 탐색한다.
코드
# 백준 5639 - 이진 검색 트리 # 분류 : 트리 import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline preorder = [] while True : try : preorder.append(int(input())) except : break def postorder(start, end) : if start >= end : return root = preorder[start] right = start + 1 while right < end and preorder[right] < root : right += 1 postorder(start + 1, right) postorder(right, end) print(root) postorder(0, len(preorder))
이 글은
(새창열림)
본 저작자 표시, 비영리 규칙 하에 배포할 수 있습니다. 자세한 내용은 Creative Commons 라이선스를 확인하세요.
Creative Commons
본 저작자 표시
비영리
'Programming > 백준' 카테고리의 다른 글
[골드 1] 백준 2263 - 트리의 순회 (파이썬) (0) | 2025.05.09 |
---|---|
[실버 2] 백준 25186 - INFP 두람 (파이썬) (0) | 2025.05.09 |
[골드 5] 백준 1916 - 최소비용 구하기 (파이썬) (0) | 2025.05.08 |
[실버 1] 백준 27970 - OX (파이썬) (0) | 2025.05.08 |
[실버 1] 백준 1697 - 숨바꼭질 (파이썬) (0) | 2025.05.08 |
댓글
이 글 공유하기
다른 글
-
[골드 1] 백준 2263 - 트리의 순회 (파이썬)
[골드 1] 백준 2263 - 트리의 순회 (파이썬)
2025.05.09 -
[실버 2] 백준 25186 - INFP 두람 (파이썬)
[실버 2] 백준 25186 - INFP 두람 (파이썬)
2025.05.09 -
[골드 5] 백준 1916 - 최소비용 구하기 (파이썬)
[골드 5] 백준 1916 - 최소비용 구하기 (파이썬)
2025.05.08 -
[실버 1] 백준 27970 - OX (파이썬)
[실버 1] 백준 27970 - OX (파이썬)
2025.05.08
댓글을 사용할 수 없습니다.