[JAVA] 백준 4256번 트리

[HAVE TO DO]

STUDYING : JAVA

---

문제링크 : www.acmicpc.net/problem/4256

 

 

BT를 전위 순회, 중위 순회한 결과가 주어진다. 즉, 위의 함수 중 preorder(root node of BT)와 inorder(root node of BT)를 호출해서 만든 리스트가 주어진다. 두 순회한 결과를 가지고 다시 BT를 만들 수 있다. BT의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 프로그램을 작성하시오.

 

예를 들어, 위의 그림을 전위 순회하면 3,6,5,4,8,7,1,2, 중위 순회하면 5,6,8,4,3,1,2,7이 된다. 이를 이용해 후위 순회하면 5,8,4,6,2,1,7,3이 된다.

 

전위 순회 : 3 6 5 4 8 7 1 2

중위 순회 : 5 6 8 4 3 1 2 7

후위 순회 : 5 8 4 6 2 1 7 3

 

전위는 맨 앞에 루트가 출력되고 left child -> right child 순회, 중위는 left child를 전부 순회한 다음에 루트 출력 후 right child를 순회한다. 후위는 left child -> right child -> root의 순서.

 

그리고 후위 순회는 left child의 왼쪽 끝부터 출력을 한다.

 

그래서 풀이는

 

전위 : 3 (root) / 6 5 4 8 (left) / 7 1 2 (right)

중위 : 5 6 8 4 (left) / 3 (root) / 1 2 7 (right)

 

left만 쪼개서 더 쪼개면

 

전위 : 6 (root) / 5 (left) / 4 8 (right)

중위 : 5 (left) / 6 (root) / 8 4 (right)

 

다시 left만 쪼개면

 

전위 : 5

중위 : 5

-> 5 출력

 

이후, 다시 6이 root인 상태로 올라가서 right를 순회하여 출력하면 된다.

 

전위 : 4 (root) / 8 (left)

중위 : 8 (left) / 4 (root)

 

전위 : 8

중위 : 8

-> 8출력

 

결국, 재귀를 사용해서 left child 돌고 right child를 돌며 출력하면 된다.

preorder의 맨 앞은 항상 root이기 때문에 이것을 사용해서 inorder의 root 위치를 알아내면 root의 앞은 left child이고, root의 뒤는 right child이다.

 

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

public class Main {
	
	static int N;
	static int node;
	static int[] preorder;
	static int[] inorder;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		
		for (int i = 0; i < N; i++) {
			node = Integer.parseInt(br.readLine());
			preorder = new int[node];
			inorder = new int[node];
			
			st = new StringTokenizer(br.readLine());
			for(int j = 0; j < node; j++) {
				preorder[j] = Integer.parseInt(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());			
			for(int j = 0; j < node; j++) {
				inorder[j] = Integer.parseInt(st.nextToken());
			}
			
			postorder(preorder, inorder);
			System.out.print("\n");
		}
		
		
	}
	
	static void postorder(int[] pre, int[] in) {
		int num = pre.length;
		if(num == 0) return;
		
		int root = pre[0];
		
        	//left child 개수 찾기
		int i;
		for (i = 0; i < num; i++) {
			if(root == in[i]) break;
		}
		
		int left = i;
		
        	//left가 0개면 방문할 필요 없음
		if(left != 0) {
			postorder(slice(pre, 1, left), slice(in, 0, left - 1));
		}
        
       	 	//right = num - left - 1, right가 0개면 방문할 필요 없음
		if(num - left - 1 != 0) {
			postorder(slice(pre, left + 1, num - 1), slice(in, left + 1, num - 1));
		}
		
		System.out.print(root + " ");
	}
	
	static int[] slice(int[] x, int s, int e) {
		int[] temp = new int[e - s + 1];
		int j = 0;
		for (int i = s; i <= e; i++) {
			temp[j] = x[i];
			j++;
		}
		return temp;
	}

}