[SWEA - Java] 1231. 중위순회

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD 

설명

트리를 구성할 때는 1차원 배열, 2차원 배열, 클래스 등 다양한 방법으로 구현할 수 있다.

 

[Java] 트리(tree) 구현 - 1차원 배열 / 2차원 배열 / 클래스 3가지 방법 구현

 

 

이 문제는 1번 노드부터 완전 이진트리 형식으로 주어지기 때문에 1차원 배열만으로도 중위 순회를 처리할 수 있다.

따라서 배열의 각 인덱스에 해당하는 알파벳 값을 저장하고 재귀를 이용해 순회할 수 있다.

N번 노드의 왼쪽 자식 노드는 N * 2번 노드, 오른쪽 자식 노드는 N * 2 + 1번 노드가 된다.

중위 순회는 왼쪽 자식 노드 → 부모노드 → 오른쪽 자식 노드 순으로 트리를 순회한다.

따라서 N * 2 + 1번 → N번 → N * 2번 노드의 순으로 순회하면 된다.

전체 코드

import java.io.BufferedReadermport java.io.BufferedReaderㅑ;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static char[] tree;
	static int N;
	static StringBuilder sb;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		sb = new StringBuilder();

		int T = 10;

		for(int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine());

			tree = new char[N+1];

			for(int i = 1; i <= N; i++) {
				StringTokenizer st =  new StringTokenizer(br.readLine());
				
				st.nextToken();
				
				tree[i] = st.nextToken().charAt(0);
			}

			sb.append("#" + test_case + " ");
			inOrder(1);
			sb.append("\n");
		}

		System.out.println(sb.toString());
	}

	static void inOrder(int idx) { // 중위 순회 
		if(idx > N) return; 
		inOrder(2 * idx);
		sb.append(tree[idx]);
		inOrder(2 * idx + 1);
	}
	
}