백준(BOJ)(Python)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

============================================================================================

1. 전위 순회 값이 주어지면 후위 순회 값을 구해야함 
>>> 뭔가 전위 순회값으로 노드를 파악하고 파악된 노드를 후위순회로 바꿔야할 거 같음
>>> 어떻게 하느냐 ? 음.... 입력값 출력값 살펴보면 ..모르겠음 
2. 진짜 하루종일 고민해도 뭘 어케 해야할 지 감도 안 잡힘...
>>> 결국 구글링.
3. 구글링 힌트만 ! 한 결과
>>> 전위 순회에서 맨 첫번째 방문 노드는 루트 노드임
>>> 특정 기준으로 노드 리스트를 자르고, 자른 리스트의 첫번째 노드는 그 자식 트리의 루트 노드임
>>> 그 자르는 기준은... 루트노드 아래에 딸린 노드 중 루트노드 보다 큰 게 나오면 자른다

 

재귀로 해줬음. 여러 블로그보면 대부분 트리 클래스로... self어쩌구....생성자 어쩌구 하는데 이해가 안 돼서 냅다 

재귀로 풀었음

 

 

<첫 번째 실패 코드>

import sys
sys.setrecursionlimit(10**6)

### 재귀를 이용한 트리 분할하기 ###
''' 
백준 예제를 보면 
50/30 24 5 28 45 / 98 52 60 = 루트 / 왼편/ 오른편으로 나눌 수 있음
그러면 
1. 루트 : 50 , 쭉 쭉 비교하다가 루트보다 큰 수 나오면 idx_right에 저장. 루트 다음수는 idx_left에 저장
2. 재귀로 루트 계속 바꿔주기 (왼편부터)
3. 더이상 자기보다 작은 수가 없으면 출력

'''
def postOrder(start,end):
    if start > end:
        return
    div = end + 1
    for i in range(start+1,end+1):
        if bts[start]<bts[i]:
            div = i 
            break
    postOrder(start+1,div-1)
    postOrder(div,end)
    print(bts[start])
    
### 입력 리스트 생성 ###
bts = []
### 리스트 입력 ###
while True:
    try:
        input = int(input())
    except:
        break
    bts.append(input)
    
### 후위순회 출력 ###
postOrder(0,len(bts))​

틀린 이유는 input이란 변수명을 사용해서엿다  ㅡ3ㅡ 

import sys
sys.setrecursionlimit(10**6)

### 재귀를 이용한 트리 분할하기 ###
''' 
백준 예제를 보면 
50/30 24 5 28 45 / 98 52 60 = 루트 / 왼편/ 오른편으로 나눌 수 있음
그러면 
1. try ,except로 정수 입력이 없을 때 까지 받아주기
2. 입력 리스트에 전위 순회 저장
3. 재귀의 시작지점과 끝지점 넘겨주기. len -1은 리스트 인덱스를 넘겨줘야하기 때문에 끝 수 인덱스는 길이 -1임
4. PostOrder > 시작지점과 끝지점을 넘겨받고, 
   만약 시작지점이 끝지점보다 크면 더이상 할 게 없으므로 끝내기
   div변수는 처음에는 끝지점보다 큰 인덱스로 지정해줌 ( 루트가 제일 큰 값일 때를 대비해서)
5. 루트 다음수 부터 div 앞 까지 비교. 큰 수 나오면 왼쪽값 오른쪽값 나눠서 따로 또 재귀해줌


'''
def postOrder(start,end):
    if start > end:
        return
    div = end + 1
    for i in range(start+1,end+1):
        if bts[start]<bts[i]:
            div = i 
            break
    postOrder(start+1,div-1)
    postOrder(div,end)
    print(bts[start]) #
    
### 입력 리스트 생성 ###
bts = []
### 리스트 입력 ###
while True:             #1
    try:
        n = int(input()) 
    except:
        break     
    bts.append(n)       #2
    
### 후위순회 출력 ###
postOrder(0,len(bts)-1) #3

일케해주면 정답!