Today's special moments become memories of tomorrow.

BOJ

[백준 9934번] 완전 이진 트리 (java)

lotus lee 2021. 3. 23. 17:36

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