[SWEA 1231] 중위순회 C++/Java

 

SW Expert Academy

 

문제풀이

 

 

특정 단어를 트리 형태로 구성한 것을 in-order 형식으로 순회하여 원래 단어를 알아내는 문제다.

 

 

[제약사항]

 

총 10개의 테스트 케이스가 주어지며, 총 노드의 개수는 100개를 넘어가지 않는다.

트리는 완전 이진 트리 형식으로 주어지며, 노드당 하나의 알파벳만 저장할 수 있다.

노드가 주어지는 순서는 위 그림과 같은 숫자 번호대로 주어진다.

 

 

 

트리가 갖는 정점의 총 수를 N이라 할 때, 트리가 완전 이진 트리 형식이기 때문에 N/2번 이하인 정점들만 자식을 가진다.

정점수가 짝수개인 경우에 N/2번째 정점은 왼쪽 그림에서 보이는 것처럼 왼쪽 자식만 가지고 있고, 홀수개인 경우에는 오른쪽 그림과 같이 왼쪽, 오른쪽 자식 모두 가지고 있다.

 

 

중위 순회는 왼쪽 서브 트리, 노드, 오른쪽 서브 트리 순으로 방문한다.

간단하게 재귀로 구현할 수 있다.

 

 

코드

 

C++ 코드

 

 

Java 코드