[백준] 5639.이진 검색 트리

문제

 

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

5639번: 이진 검색 트리

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

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

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

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

 

입력

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

 

출력

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

 

예제

입력	출력
50 30 24 5 28 45 98 52 60	5 28 24 45 30 60 52 98 50

 

문제풀이 코드

# 시간초과
class TreeNode:
    def __init__(self, val = 0, left = None, right = None):
        self.val = val
        self.left = left
        self.right = right

class BST:
    def __init__(self, head):
        self.head = head

    def insert(self, value):
        self.current = self.head
        while True:
            if value < self.current.val:
                if self.current.left != None:
                    self.current = self.current.left
                else:
                    self.current.left = TreeNode(value)
                    break
            else:
                if self.current.right != None:
                    self.current = self.current.right
                else:
                    self.current.right = TreeNode(value)
                    break

    def postOrder(self, node):
        if node == None:
            return
    
        self.postOrder(node.left)

        self.postOrder(node.right)

        print(node.val)
    
    
lst = []
while True:
    try:
        lst.append(int(input()))
    except:
        break

bst = BST(TreeNode(lst[0]))

for i in range(1, len(lst)):
    bst.insert(lst[i])

bst.postOrder(bst.head)

트리를 생성하고 탐색하는 방식으로 접근

1. 전위순회된 결과를통해 이진 검색 트리를 생성한다.

2. 생성된 이진 검색 트리를 후위순회하여 결과를 반환한다

** 시간초과로 통과하지 못했다..

 

 

import sys
sys.setrecursionlimit(1000000)

lst = []
while True:
    try:
        lst.append(int(input()))
    except:
        break

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

postorder(0,len(lst)-1)

다른 사람 코드를 참고해서 문제 풀이

이진 탐색 트리기때문에 주어진 배열에서 현재 값보다 큰 값을 마주칠때부터 현재 노드의 오른쪽 노드가 된다.

현재 값보다 큰 값을 만났을 때 mid를 i값으로 바꿔준다.(i - 1까지가 현재 노드의 left노드)

[start + 1:mid -1] 이 현재 노드의 left노드이고

[mid:end]는 현재 노드의 right노드이다

이 과정을 재귀적으로 반복하면서 트리를 새로 구성하지않고 주어진 트리를 후위순회할 수 있다.

 

예제 해결 과정