BOJ 5639번: 이진 검색 트리

www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

아이디어:

모르겠어서 구글링했다.

전위순회니까 입력받는대로 노드를 삽입하면 그래프를 구할 수 있었다.

그.런.데. 정석대로(?) 풀면 파이썬은 시간 초과가 났다..

#시간초과
import sys
sys.setrecursionlimit(10**9)

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

def putNode(n, cur):
    while (True):
        if (n<cur.val):
            if (cur.left!=None):
                cur = cur.left
            else:
                cur.left = Node(n)
                break
        elif (n>cur.val):
            if (cur.right!=None):
                cur = cur.right
            else:
                cur.right=Node(n)
                break
            
def postorder(tree):
    if (tree.left!=None):
        postorder(tree.left)
    if (tree.right!=None):
        postorder(tree.right)
    print(tree.val)

#트리 루트
root = int(sys.stdin.readline())
tree = Node(root)
cur = tree

while (True):
    #파이썬 예외처리
    try:
        n = int(sys.stdin.readline())
        putNode(n, tree)
    except: break
        
postorder(tree)  

 

그래서 루트를 기준으로 루트보다 작은 건 왼쪽 서브트리, 큰 건 오른쪽 서브트리로 나누고, 그 각각의 서브트리의 첫번째 원소가 그 서브트리의 루트가 되니까 후위순위로 출력하려면 왼쪽으로 나누고, 그다음 오른쪽으로 나누고, 맨 마지막에 루트를 출력하면 된다. 이 방법또한 재귀함수를 이용하였고, 이분탐색을 이용하였다.

 

import sys
sys.setrecursionlimit(10**9)

arr = []
while(True):
    try:
        arr.append(int(sys.stdin.readline()))
    except:
        break

def solve(start, end):
    if (start>end): return

    div = end+1
    
    for i in range(start+1, end+1):
        if (arr[start]<arr[i]):
            div = i
            break
    solve(start+1, div-1)
    solve(div, end)
    print(arr[start])
solve(0,len(arr)-1)