5639 파이썬- 트리

배열상에서 생각 하려하지 않고 트리에만 집중하다가 시간 많이 날렸다ㅠㅠ

구글링참고해 풀어서 나중에 다시 한번 풀어보기!!

 

트리 순회의 핵심은 루트노드, 왼쪽트리, 오른쪽 트리 이렇게 세 개로 나누어 재귀함수 이용해 진행해야 한다는 점이다

-> 이 문제의 경우 몇 번째 인덱스부터 몇 번째 인덱스까지가 왼쪽트리,  몇 번째 인덱스부터 몇 번째 인덱스까지가 오른쪽 트리인지 인덱스 구해 재귀함수 거치게 해주면 된당

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

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

def post(start, end):
    if start > end:
        return
    mid = end + 1
    for i in range(start + 1, end + 1):
        if tree[i] > tree[start]:
            mid = i
            break
    post(start + 1, mid - 1) #왼쪽 트리
    post(mid, end) #오른쪽 트리
    print(tree[start]) #루트 노드

post(0, len(tree) - 1)

 

 

<세부설명>

 

* 계속 입력을 받되, 숫자가 아닌 값을 입력하면 입력을 그만 받도록 구현하는 것부터 막혀서 구글링을 통해 알아냄!!

while True:
    try:
        tree.append(int(input()))
    except:
        break

 

* 어디까지를 왼쪽트리인지 하기 위해 mid 값을 구해야 하는데 여기가 키 포인트

 

* mid=end+1로 초기화 하는 이유 (바로 이해 안됐던 부분)

-> 오른쪽 자식 노드가 비어 mid 값이 없는 경우 오류 나지 않게 하기 위해 mid값을 default값으로 설정해주어야 하는데,

   이때 왜 하필 end+1로 초기화하냐면 언제 이 함수를 끝내줄지 정해야해서!!!!! 계속 재귀함수 돌게 할 수 없어서 끝내야함

   끝내주기 위해 특이점을 만들고 이를 mid=end+1로 하고 start>end면 끝낸다는 조건을 추가해주어 함수 끝내는 지점을       정해줌

-> 재귀함수는 항상 언제 끝내줄 지 조건을 통해 지정해주어야함을 잊지말기!!