9934번: 완전 이진 트리
상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래
www.acmicpc.net
중위순회한 결과가 주어지면 트리의 구조를 출력하는 문제이다.
중위순회의 특징을 알면 쉽게 문제를 풀 수 있다. 중위순회한 결과에서 가운데 값은 해당 트리의 루트에 해당한다.
1 - 6 - 4 - 3 - 5 - 2 - 7
즉, 전체 트리에 루트 노드는 3번이다.
그 다음 3을 기준으로 왼쪽(1 - 6 - 4)는 왼쪽 자식 트리를 중위순회한 결과이며, 오른쪽(5 - 2 - 7)은
오른쪽 자식 트리를 중위순회한 결과이다. 각각의 자식 트리도 마찬가지로 가운데 값이 부모노드일 것이다.
1 - 6 - 4 5 - 2 - 7
이런식으로 재귀를 이용하여 문제를 해결하였다.
트리의 높이를 크기로 하는 StringBuffer 배열을 생성하였다.
StringBuffer[] ans = new StringBuffer();
ans[0] : 트리의 첫번째 높이 -> 3
ans[1] : 트리의 두번째 높이 -> 6 2
ans[2] : 트리의 세번째 높이 -> 1 4 5 7
재귀함수의 매개변수로 현재 노드가 트리의 몇층(floor)에 해당하는지를 넣어준 후, 해당하는 노드의 번호를
ans[floor] 문자열 뒤에 추가해준다.
정답코드 :
'BOJ' 카테고리의 다른 글
| [백준 14725번] 개미굴 (java) (0) | 2021.03.25 |
|---|---|
| [백준 2098번] 외판원 순회 (java) (1) | 2021.03.23 |
| [백준 1719번] 택배 (java) (0) | 2021.03.23 |
| [백준 5670번] 휴대폰 자판 (java) (0) | 2021.03.21 |
| [백준 2491번] 수열 (java) (0) | 2021.03.19 |