[BOJ 2263] 트리의 순회 C++/Kotlin

 

2263번: 트리의 순회

 

동꿀오소리님 풀이 참고

[백준] 2263번 트리의 순회 - C++ - DGOS | 동꿀오소리

 

 

문제풀이

 

이진 트리의 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제이다.

위 트리의 인오더, 포스트오더, 프리오더를 살펴보자.

 

중위 순회 : 5 6 8 4 3 1 2 7

후위 순회 : 5 8 4 6 2 1 7 3

전위 순회 : 3 6 5 4 8 7 1 2

 

굵게 표시해놓은 것이 루트 노드이다.

후위 순회는 [왼쪽 자식 - 오른쪽 자식 - 루트]순으로 순회하기 때문에 루트가 항상 마지막이다.

따라서 중위 순회 값의 인덱스를 따로 저장해두면 중위 순회에서의 루트 노드의 인덱스를 쉽게 찾을 수 있다.

 

찾아낸 루트 값을 출력해주고 더 이상 분해할 수 없을 때까지 트리의 왼쪽과 오른쪽을 탐색해주면 전위 순회를 구할 수 있다.

 

 

코드

 

C++ 코드

 

 

Kotlin 코드