[백준 5639번] 파이썬 - 이진 검색 트리

http://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

 

 

# 조건

• 이진 검색 트리는 아래와 같은 조건을 만족하는 이진 트리
  • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
  • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
  • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
• 전위 순회 (루트-왼쪽-오른쪽)
• 후위 순회 (왼쪽-오른쪽-루트)

 

• 아래 이진 검색 트리의 전위 순회 결과
  • 50 30 24 5 28 45 98 52 60
• 후위 순회 결과
  • 5 28 24 45 30 60 52 98 50
• 전위 순회한 결과가 주어졌을 때, 후위 순회한 결과를 구하는 프로그램을 작성

 

 

입력

• 전위 순회한 결과가 주어진다.
• 노드에 들어있는 키의 값은 10^6보다 작은 양의 정수
• 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다.

 

# 접근 방법 및 Solution

• 전위 순회한 결과는 루트 노드를 시작으로하여
  • 루트 노드 보다 작다면 왼쪽 서브 트리
  • 크다면 오른쪽 서브 트리로 구성해 준다.
• 재귀를 활용하여, 현재 노드를 루트 노드로 하였을 때, 루트 노드보다 큰 수의 인덱스를 찾아주며
  • 왼쪽 루트의 경우 시작+1, 인덱스-1
  • 오른쪽 루트의 경우 인덱스, 끝 인덱스 재귀
  • 이후, 시작+1 이 끝 인덱스를 역전한 경우 return
  • 후위 순회 이므로 left, right 서브 트리를 모두 찾은 후 마지막에 찍어주면 된다.
• 입력을 받을 때 길이를 모르므로, try - except 활용

import sys  
sys.stdin = open('input.txt')  
sys.setrecursionlimit(10 ** 6)  
input = sys.stdin.readline  
  
  
def post_order(start, end):  
    if start > end:  
        return  
  
    # 루트 노드  
    root = pre_order[start]  
    idx = start + 1  
  
    # root보다 커지는 지점을 찾는 과정  
    while idx <= end:  
        if pre_order[idx] > root:  
            break  
        idx += 1  
  
    # 왼쪽 서브트리  
    post_order(start + 1, idx - 1)  
  
    # 오른쪽 서브트리  
    post_order(idx, end)  
  
    # 후위순회이므로 제일 마지막에 찍으면 된다  
    print(root)  
  
  
pre_order = []  
while 1:  
    try:  
        pre_order.append(int(input()))  
    # try에서 예외 발생시 break 실행  
    except:  
        break  
  
post_order(0, len(pre_order) - 1)

 

• 트리의 경우 많이 나오는 유형 중 하나이다.
• 전위 순회, 중위 순회, 후위 순회의 특징을 알고 -> 서로 바꾸는 연습을 많이 해보아야 할 것 같다.
• 또한, 재귀에 적합한 자료 구조 이므로 재귀에 대해 이해하는 것도 중요!!