파이썬 백준 5639 이진 검색 트리

import sys sys.setrecursionlimit(10**8) input = sys.stdin.readline l = [] while True:     try:         l.append(int(input()))     except:         break def DAC(left, right) :     if left > right :         return     if left == right :         print(l[left])         return     i = left + 1     if l[right] < l[left] :         DAC(left + 1, right)     else :         while i <= right and l[i] < l[left] :             i = i + 1         DAC(left + 1, i - 1)         DAC(i, right)     print(l[left]) DAC(0, len(l) - 1)

처음엔 입력값으로부터 트리를 만들어서 그걸 후위 순회하며 출력했는데 시간초과가 떴다.

리스트 길이가 10000밖에 안되니 될 줄 알았는데 뭔가 작업량이 많나보다.

그래서 문제의 '왼쪽, 오른쪽 서브 트리도 이진 트리이다'라는 데에서 영감을 얻어 분할 정복으로 접근했다.

 

트리 구조의 리스트에서 [0]은 루트이고 [1]은 루트의 왼쪽 자식이다.

그리고 리스트의 왼쪽부터 차례대로 체크했을 때 가장 처음으로 루트보다 큰 원소가 루트의 오른쪽 자식이다.

이를 이용하여 [1]부터 [i-1]까지, [i]부터 [-1]의 두 부분으로 나뉘어 재귀하는 함수를 정의했다.

리스트의 길이가 1이 되어 더이상 자식이 없으면 자신을 출력하며 재귀함수를 닫고 윗 단계로 돌아간다.

이때 루트를 프린트하는 구문은 재귀함수보다 밑에 있어야 후위 순회가 된다.