이진 검색 트리 #5639

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

50
30
24
5
28
45
98
52
60

예제 출력 1 복사

5
28
24
45
30
60
52
98
50

출처

ICPC > Regionals > Asia Pacific > Thailand > 2011 ACM-ICPC Asia Phuket Regional Programming Contest B번

• 문제를 번역한 사람: baekjoon

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 트리
• 재귀

---

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

'''
1. 아이디어 :
    1) (시간초과...왜???) 입력값들을 이진트리에 넣는다. 후위순회를 재귀를 이용하여 구현.
    2) 첫번쨰 입력값이 root니까, 재귀용법으로 root 기준으로 둘로 나눈다. root제외 다른 값이 없으면 출력.
2. 시간복잡도 :
    1) O(n) + O(n) + O(n) = O(n)
    - 입력 받아서 리스트에 넣는 시간복잡도 : O(n), 이진트리에 입력하는 시간복잡도 : O(n), 후위순회 : O(n)
    2) O(n) + O(n) = O(n)
    - 입력 받아서 리스트에 넣는 시간복잡도 : O(n), 재귀함수 안에 for문.
3. 자료구조 :
    1) 이진 검색 트리
'''

import sys
sys.setrecursionlimit(10**9)
nums = []
while True:
    try:
        nums.append(int(sys.stdin.readline()))
    except:
        break
def dfs(start, end):
    if start > end:
        return
    base = nums[start]
    mid = end+1
    for i in range(start+1, end+1):
        if base < nums[i]:
            mid = i
            break

    dfs(start+1, mid-1)
    dfs(mid, end)
    print(base)

dfs(0, len(nums)-1)

'''


2)
import sys
input = sys.stdin.readline

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

    def insert(self, val):
        if not self.val:
            self.val = val
            return

        if self.val == val:
            return

        if val < self.val:
            if self.left:
                self.left.insert(val)
                return
            self.left = Node(val)
            return
        elif val > self.val:
            if self.right:
                self.right.insert(val)
                return
            self.right = Node(val)



def postorder(node):
    if node.left:
        postorder(node.left)
    if node.right:
        postorder(node.right)
    print(node.val)

import sys
sys.setrecursionlimit(10**9)
nums = []
while True:
    try:
        nums.append(int(sys.stdin.readline()))
    except:
        break

root = Node(nums[0])
for i in range(1, len(nums)):
    root.insert(nums[i])

postorder(root)

len = 9
50, [30,24,5,28,45] [98,52,60]

30 [24,5,28] [45]    98 [52,60] []

24 [5] [28]    45 [] []     52  [60]

5 [] []     28 [] []     45 [] []     60 [] []
'''