백준 : 4256 트리

www.acmicpc.net/problem/4256

4256번: 트리

전위 순회 : root , 왼쪽 ,오른쪽

중위 순회 : 왼쪽 root 오른쪽

후위 순회 : 왼쪽 오른쪽 root

 

주어지는건 전위와 중위이다.

전위 특징 : 첫번째에 root가 나온다. 따라서 전위 순회에서 맨앞은 후위 순회에서 맨뒤에 나온다.

 

이젠 전위 순회를 왼쪽 지점 오른쪽 지점을 다시 새로운 전위순회로 쪼개주면됨.. 

따라서 중위순회에서 root값을 스택형식으로 출력하면서 그 root값 중심으로 좌우를 나눠주는 작업을 하면 알고리즘 완성.

 

알고리즘 분류  : DFS , 스택

package boj;

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

public class boj4256 {
	static int N;
	static int[] pre;
	static int[] in;

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

		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());
			pre = new int[N];
			in = new int[N];

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				pre[i] = Integer.parseInt(st.nextToken());
			}
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N; i++) {
				in[i] = Integer.parseInt(st.nextToken());
			}
			post(0, N, 0, sb);
			sb.append('\n');
		}
		System.out.println(sb.toString());
	}

	private static void post(int start, int end, int cur, StringBuilder sb) {

		for (int i = start; i < end; i++) {
			if (in[i] == pre[cur]) {
				post(start, i, cur + 1, sb);
				post(i + 1, end, cur + 1 + i - start, sb);
				sb.append(pre[cur]).append(' ');
			}
		}
	}
}