중위순회한 결과가 주어지면 트리의 구조를 출력하는 문제이다.
중위순회의 특징을 알면 쉽게 문제를 풀 수 있다. 중위순회한 결과에서 가운데 값은 해당 트리의 루트에 해당한다.
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 |