[Python/백준] 5639번: 이진 검색 트리

문제

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

5639번: 이진 검색 트리

---

문제 요약

이진 검색 트리를 전위 순회(루트-왼쪽-오른쪽)한 결과가 주어졌을 때, 그 트리를 후위 순회(왼쪽-오른쪽-루트)한 결과를 출력한다.

 

이진 검색 트리란 세 가지 조건을 만족하는 이진 트리이다.

조건 1. 노드의 왼쪽 서브트리에 있는 모든 노드의 key는 노드의 key보다 작다.

조건 2. 노드의 오른쪽 서브트리에 있는 모든 노드의 key는 노드의 key보다 크다.

조건 3. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

---

코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def postorder(first, end): 
# first는 현재 트리의 루트 노드 인덱스, end는 현재 트리의 마지막 노드 인덱스 (가장 오른쪽에 있는 노드)
    #print(f"루트 노드 first는 {first}, 마지막 노드 end는 {end}")

    if first > end: # 해당 범위에 노드가 없을 때 (이전 탐색에서 mid값이 재설정되지 않았을 경우)
        return

    mid = end + 1 # 루트보다 큰 값이 존재하지 않을 경우 대비

    # 왼쪽 서브 트리와 오른쪽 서브 트리를 구분할 mid값 찾기
    for i in range(first + 1, end + 1):
        if tree[first] < tree[i]:
            mid = i # 현재 트리의 루트 노드보다 큰 값이 존재하면 mid로 설정
            break 

    postorder(first + 1, mid - 1) # 현재 트리의 왼쪽 서브트리를 후위 순회
    postorder(mid, end) # 현재 트리의 오른쪽 서브트리를 후위 순회
    print(tree[first]) # 현재 트리의 루트 노드 값 출력

tree = []

# 노드 입력 받기
# 전위 순회한 결과를 입력
while True:
    try:
        n = int(input())
        tree.append(n)
    except:
        break

#print(tree)

postorder(0, len(tree) - 1) # 루트노드 (0번) 부터 마지막 노드까지 후위 순회

---

코드 설명

1. 배열 tree에 전위 순회한 입력 값을 차례대로 저장한다.

+ EOF(End Of File) 예외 발생시 입력을 종료한다.

 

2. 트리를 후위 순회하는 postorder 함수를 정의한다.

 

2 - 1. first와 end를 인자로 받는다.

+ first: 후위 순회할 현재 트리의 루트 노드 인덱스

+ end: 후위 순회할 현재 트리의 마지막 노드 인덱스 (가장 오른쪽 노드)

 

2 - 2. first가 end보다 크다면 함수를 종료한다. (순회할 루트 노드의 자식 노드가 존재하지 않을 경우)

 

2 - 3. mid값을 생성한다. (현재 트리의 오른쪽 서브트리의 첫 번째 노드)

+ 초기 값은 end + 1: first보다 큰 값을 갖는 노드가 존재하지 않을 경우,  현재 트리를 왼쪽 서브 트리로 갖는 트리의 첫 번째 노드로 설정

 

2 - 4. 반복문을 통해 현재 트리의 루트 노드보다 큰 값을 가진 인덱스  i가 존재하면 mid를 i로 설정하고 종료한다.

 

2 - 5. 현재 트리의 왼쪽 서브 트리를 후위 순회한다. (재귀)

 

2 - 6. 현재 트리의 오른쪽 서브 트리를 후위 순회한다. (재귀)

 

2 - 7. 현재 트리의 루트 노드 값을 출력한다.

 

3. 입력 받은 트리의 루트 노드부터 마지막 노드까지 후위 순회한다.