SWEA 1231 - 중위순회

문제 링크

문제 요약

주어진 트리를 중위 순회했을 경우, 만들어지는 단어 출력

ex: SOFTWARE

접근

• 완전 이진트리이기에 입력은 트리를 배열로 저장할 때와 같은 방법으로 들어옴, 그대로 트리에 저장하면 됨
• 중위순회 : 왼쪽 노드 접근 -> 현재 노드 출력 -> 오른쪽 노드 접근 순서

정답 코드(java/자바)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class SWEA_1231 {
	static StringBuilder sb = new StringBuilder();
	static char[] tree;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testCase = 11;
		int n,n1, tmp, idx, cnt;
		String[] str;
		for(int tc = 1; tc < testCase; tc++){
			//출력 포맷
			sb.append('#').append(tc).append(" ");
			
			// 트리의 노드 수 입력받기
			n = Integer.parseInt(br.readLine());
			n1 = n + 1;
			
			// 트리를 저장할 배열
			tree = new char[n1];
			
			//트리 입력받기
			for(int i = 1; i < n1; i++) {
				str = br.readLine().split(" ");
				tmp = Integer.parseInt(str[0]);
				// 해당 노드의 위치에 char 저장
				tree[tmp] = str[1].charAt(0);
			}
			
			// 중위순회 - 재귀를 통해 구현
			inorder(1, n1);
			
			sb.append('\n');
		}
		System.out.println(sb);
		
	}

	//중위순회 : 왼쪽 노드 먼저 방문 -> 출력 -> 오른쪾 노드 방문
	private static void inorder(int idx, int n) {
		if(idx * 2 < n) {
			inorder(idx*2, n);
		}
		sb.append(tree[idx]);
		if(idx * 2 + 1 < n) {
			inorder(idx * 2 + 1, n);
		}
	}

}