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

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

5639번: 이진 검색 트리

트리 재귀 순회 문제이다. 이런 문제를 몇번 풀어보긴 했지만, 익숙하지 않아서 꽤 애를 먹었다.

알고리즘은 뭔가 답답할 땐 항상 그림을 그리며 직접 손으로 따라가보자!

 

--설명--

1. (0,8)을 넘겨준다

2. mid는 end+1로 설정하고, ( 아래 for문에서 mid값이 갱신되지 않는다면, end를 그대로 넘겨야 하는데 넘길 때 -1을 해주므로 )

3. start를 pivot 삼아서 for문을 돌리는데, 이때 더 큰 값 = 현재 트리의 왼쪽 서브트리 중 가장 오른쪽에 있는 값을 만나면 값을 갱신해준 뒤 왼쪽 서브트리에 대한 탐색을 진행한다. 

4. 3번에서 왼쪽 서브트리 범위를 구했으므로 남은 범위는 오른쪽 서브트리 범위이다.

5. 마지막으로 해당 트리의 루트를 출력해준다

 

문제의 예시를 이용하자면 해당 예시의 스택은 다음과 같다 (숫자는 입력 배열의 인덱스임 !!)

postorder(0,8) -> postorder(1,5) | postorder(6,8) | print(0) -> postorder(2,4) | postorder(5,5) | print(1) -> postorder(3,3) | postorder (4,4)  | print(2) 여기서 이제 5,28,24가 출력되고,

postorder(2,4) 다음인 (5,5)로 돌아가서 호출하여 45가 출력되고, print(1)도 수행되어 30이 출력된다.

 

이제 postorder(1,5) 예하의 수행이 모두 끝났으므로 postorder(6,8)이 호출된다.

postorder(7,8) | postorder(9,8) | print(6) -> postorder(8,7) | postorder(8,8) | print(7) 이 수행된다.

이때 start가 end보다 크다면 for문 자체도 돌아가지 않고, 의미가 없으므로 바로 return해준다.

 

그럼 (8,7)이 return되어 (8,8)이 실행되어 60이 출력되고, print(7)이 수행되어 52가 출력된다.

이제 postorder(7,8) 예하 수행이 모두 끝났는데, (9,8)은 start가 end보다 커서 바로 return되므로 print(6)이 수행되어 98이 출력.

 

이제 postorder(6,8)도 모두 끝났으므로 마지막인 print(0)이 출력되어 50이 출력되고 종료 된다.

 

약간 야매지만, return여부를 검사하는 if문에서 start와 end가 동일하면 출력시켜주고 return했다.

사실 굳이 하지 않아도 start와 end가 동일하면 마지막 print(tree[start]) 코드에 의해 출력되지만, 재귀 탐색을 한번 더 해야하기 때문에 이를 방지하고자 바로 출력시켜주었다.

import sys
#from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def postorder(start, end):
    if start >= end: 
        if start == end:
            print(tree[end])
        return
    
    mid = end+1
    
    for i in range(start+1,end+1):
        if tree[i] > tree[start]:
            mid = i
            break
        
    postorder(start+1,mid-1)
    postorder(mid,end)
    print(tree[start])

if __name__ == "__main__":
    tree = []
    
    while True:
        try:
            tree.append(int(input()))
        except:break
        
    postorder(0,len(tree)-1)