[백준] 12865번 이진 검색 트리 [Python]

 

 

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 문제

 

이진 검색 트리

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

이진 검색 트리

 

전위 순회: 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리

후위 순회: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트

 

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 $($루트-왼쪽-오른쪽$)$은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 $($왼쪽-오른쪽-루트$)$는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

입력

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

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

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

 

첫 숫자 : 이진 트리의 루트

i번째 숫자 $n_i$와 i+1 번째 숫자 $n_{i+1}$에 대해서

$n_i$ > $n_{i+1}$ 이면 $n_{i+1}$는 $n_i$의 왼쪽 서브트리이다.

$n_i$ < $n_{i+1}$ 이면 $n_{i+1}$는 $n_i$ 또는 그 상위 루트의 오른쪽 서브트리이다.

 

한 루트에 대해서 왼쪽 서브트리와 오른쪽 서브트리에 대해서 루트의 다음 노드부터 존재한다면 왼쪽, 오른쪽 순서대로 후위 순회 하는 함수 f로 탐색을 하고, 끝나고 그 루트를 출력한다.

위 과정을 반복하면 왼쪽, 오른쪽, 루트 순서대로 출력 할 수 있다.

 

import sys
sys.setrecursionlimit(10000*2)

def main():
    # 노드의 개수가 주어지지 않아서 주어진 모든 노드를 입력 받음
    # li = [int(n) for n in open(0).readlines()]
    li = []
    while True:
        try:
            li.append(int(sys.stdin.readline()))
        except:
            break

    def f(s, e):
        if s >= e: 
            print(li[s])
            return
        
        # 모든 노드가 시작 노드 보다 작을 때 -> 오른쪽 서브 트리 존재 x
        # 다음 노드가 시작 노드보다 클 때 -> 왼쪽 서브 트리 존재 x
        if li[s] > li[e] or li[s] < li[s+1]:
            # 다음 노드 부터 다시 탐색 
            f(s+1, e)
            
            # 루트를 마지막으로 출력 후 현 함수 종료
            print(li[s])
            return
        
        # 왼쪽, 오른쪽 서브 트리가 둘 다 존재하는 경우
        for i in range(s+1, e+1):
        	# 왼쪽 서브트리가 존재하지 않는 곳까지 탐색 후
            # 그 노드를 기점으로 나누어 탐색 시작
            if li[s] < li[i]:
                f(s+1, i-1)
                f(i, e)
                break
                
        # 루트를 마지막으로 출력
        print(li[s])

    f(0, len(li)-1)

if __name__ == "__main__":
    main()

 

예제 입력 1 

50
30
24
5
28
45
98
52
60

예제 출력 1 

5
28
24
45
30
60
52
98
50