트리. [5639]

[1. 문제 설명]

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. (재귀적임)

이진 트리의 전위 순회 결과가 있을 때,

후위 순회 결과를 출력한다.

 

 

[2. 풀이 접근]

전위 순회 결과가 주어졌을 때, 트리의 구조를 대강 알 수 있다.

 

Root [... Left sub tree....] [....Right sub tree....]

 

여기서 Right sub tree 의 시작점은

root 보다 큰 값이 시작하는 위치이므로,

간단한 탐색으로 알 수 있다.

 

Left sub tree 와 Right sub tree 에 대한 부분문제를 재귀를 이용하여 같은 방식으로 해결 할 수 있다.

 

후위 순회이므로 각 sub tree 를 처리하고 나서, root 를 출력하도록 한다.

 

유사한 문제

=> https://testkernelv2.tistory.com/354

 

 

[3. 코드]