[백준] 4256 - 트리

[문제링크]

4256번: 트리

 

1. 현재 노드 x를 기준으로, 전위 순회는 x-[왼쪽]-[오른쪽] 의 순서로, 중위 순회는 [왼쪽]-x-[오른쪽]의 순서로 만들어진다

 

2. 즉, 전위 순회 결과의 첫 노드를 기준으로, 중위 순회의 왼쪽과 오른쪽을 분리할 수 있다.

 

3. 또한 왼쪽과 오른쪽 subtree에 대해서도 동일한 작업으로 분리할 수 있다.

• 최종적으로 tree의 크기가 1이 되면, leaf 노드가 된다

 

4. tree를 입력받아, root 노드를 만들어 반환하는 함수를 만들 수 있다.

• 두 자식 노드는 동일 함수에 left/right subtree에 대해 재귀 돌려 구할 수 있다.

 

5. 이때 재귀 순서를 왼쪽->오른쪽으로 진행하면, 전위 순회와 진행 순서가 일치하게 된다

• 즉, 매 재귀 단계마다 전위순회의 다음번 노드가 곧 root노드가 된다 (전역변수로 관리)
• 중위 순회의 left/right만 관리하면 된다

 

6. 복원한 원형 tree로부터 후위 순회 결과를 얻어낸다

 

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

public class Main{
	
	static class node{
		int num;
		node left;
		node right;
		node(int num){
			this.num=num;
		}
	}
	static int cnt;
	static int[] pre;
	static int[] in;
	static StringBuilder sb;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int tc = pint(br.readLine());
		for (int test = 1; test <= tc; test++) {
			int n = pint(br.readLine());
			pre = new int[n];
			in = new int[n];
			cnt=0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < n; j++) {
				pre[j]=pint(st.nextToken());
				in[j]=pint(st2.nextToken());
			}
			
			node head = restore(0, n); //restore original tree
			
			sb = new StringBuilder();
			postorder(head);
			System.out.println(sb);
		}
	}
	
	static node restore(int s, int e) {
		if(s==e)return null; //leaf node
		int cur = pre[cnt++]; //head of current subtree
		node n = new node(cur); //node
		for (int i = s; i < e; i++) {
			if(cur==in[i]) {
				n.left=restore(s, i); //left child
				n.right=restore(i+1, e); //right child
			}
		}
		
		return n;
	}
	
	static void postorder (node n) {
		if(n.left!=null)postorder(n.left);
		if(n.right!=null)postorder(n.right);
		sb.append(n.num).append(" ");
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면