[백준] 5639.이진 검색 트리 (Swift)

코딩테스트/백준

도지대디 2022. 5. 24. 01:37

5639번: 이진 검색 트리

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다

www.acmicpc.net

풀이

전위순회 입력대로 트리를 구성하여 후위순회로 출력하는 방법은 시간초과가 발생합니다.

따라서 전위순회 결과에서 규칙을 찾는 과정이 필요한 문제입니다.

전위순회는 루트 노드로부터 시작해 왼쪽 자식, 오른쪽 자식 순으로 진행되기 때문에 전위순회의 가장 첫번째 값은 루트 노드가 됩니다.

이진 탐색 트리의 특성 상 왼쪽 자식은 루트노드보다 무조건 값이 작기 때문에 전위순회 값이 루트노드보다 값이 작은 동안은 왼쪽 서브트리가 됩니다.

또한 오른쪽 자식은 루트노드보다 무조건 값이 크기 때문에 전위순회 값이 루트노드보다 큰 경우 오른쪽 서브트리가 됩니다.

이진 탐색 트리는 여러 갈래로 쪼개도 계속 그 성질을 유지하기 때문에 아래 그림처럼 계속하여 분할할 수 있습니다.

이렇게 모두 분할한 트리 중 왼쪽 서브트리에서부터 왼쪽자식 -> 오른쪽자식 -> 루트노드 순으로 순회을 해준다면 트리의 후위순회를 출력할 수 있습니다.