[백준] 5639: 이진 검색 트리

이진 트리의 순회 방식

전위 순회(DLR) ✔️

데이터->왼쪽노드->오른쪽노드 순서

중위 순회(LDR)

왼쪽노드->데이터->오른쪽노드 순서

후위 순회(LRD) ✔️

왼쪽노드->오른쪽노드->데이터 순서

🔗 문제 링크: https://www.acmicpc.net/problem/5639

풀이

전위 순회의 첫 원소는 루트임!

💡 idea: 이진 트리를 구해서 후위 순회하기

시간 초과... 이진 트리를 만드는 시간 + 후위 순회에 걸리는 시간이라서 시간 초과가 난다.

💡 전위 순회 결과를 최대한 활용하자!

전위 순회의 첫 원소가 루트 노드이고, 루트 노드의 다음 노드가 루트보다 작으면 왼쪽, 루트보다 크면 오른쪽으로 나뉜다. 참고한 글