[백준/Python] 이진 검색 트리

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

 

---

입력, 재귀를 위한 limit 제한

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

 

1. 트리 만들어서 postorder 하기

2. 트리 없이 리스트로 postorder 하기

3. 인덱스를 이용해서 postorder하기

 

 

 

1. 트리 만들어서 postorder 하기

 

트리 클래스 생성

class Node:
    def __init__(self, node):
        self.node = node
        self.left = None
        self.right = None
    
    # 추가 함수
    def plus(self, res): # res: 들어오는 값
        if self.node > res.node: # 현재 값보다 작으면 왼쪽으로
            # 왼쪽 값이 None이면 거기에 넣는다
            if self.left == None:
                self.left = res
            # 현재 값의 왼쪽 값으로 다시
            else:
                self.left.plus(res)
        else:					# 현재 값보다 크면 오른쪽으로
            # 오른쪽 값이 None이면 거기에 넣는다
            if self.right == None:
                self.right = res
            # 현재 값의 오른쪽 값으로 다시
            else:
                self.right.plus(res)

 

 

후위순회 함수 만들기

def postorder(node):
    if node.left != None:
        postorder(node.left)    
    if node.right != None:
        postorder(node.right)
    print(node.node)

 

 

입력 및 실행 코드

i = True
while True:
    try:
        if i:
            root  = Node(int(input()))
            i = False
        else:
            a = Node(int(input()))
            root.plus(a)
    except:
        break
postorder(root)

 

이 방법은 시간 초과가 납니다

 

---

2. 트리 없이 리스트로 postorder 하기

 

https://velog.io/@nkrang/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%EC%A4%80-5639-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-%ED%92%80%EC%9D%B4-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[알고리즘] 백준 5639 '이진 검색 트리' 풀이 _ 파이썬

 

이진트리가 전위 순회로 이루어진 것을 이용한다

리스트로 만들었을 때

트리의 가운데 / 왼쪽 / 오른쪽 으로 나누어진다(위의 블로그 참고)

 

왼쪽: 가운데보다 값이 작다

오른쪽: 가운데보다 값이 크다

 

def postorder(lists):
    mid = lists[0]
    left = [i for i in lists if mid>i]
    right = [i for i in lists if mid<i]
    if len(left) != 0:
        postorder(left)
    if len(right) != 0:
        postorder(right)
    print(mid)

 

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

이렇게 되면 트리 생성 없이 postorder이 가능하다

 

 

---

3. 인덱스를 이용해서 postorder하기

 

https://sangju.tistory.com/41

백준 5639 파이썬(Python) 문제풀이 이진 검색 트리

 

 

가운데 값보다 커지는 인덱스를 찾는다

def post(start, end):
    if start > end:
        return
        
    # 가운데 값
    mid = lists[start]
    
    # end+1로 하여 큰 값이 없다면 start > end 값을 충족할 수 있도록
    change = end+1
    for i in range(start+1, end+1):
        if mid < lists[i]:
            change = i
            break
    post(start+1, change-1) # 가운데보다 작은 값
    post(change, end) # 가운데보다 큰 값
    print(mid) # 가운데

change는 가운데 값보다 큰 값의 인덱스

end + 1로 설정하는 이유는 오른쪽 서브트리가 존재하지 않는 경우,

post(change, end)를 할 때 start>end 조건이 걸릴 수 있도록 하기 위해서

 

lists = []
while True:
    try:
        lists.append(int(input()))
    except:
        break
post(0, len(lists)-1)