[백준 / Java] 2263번 : 트리의 순회

문제

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

예제 입력 1 

3
1 2 3
1 3 2

예제 출력 1 

2 1 3

https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

---

문제 풀이

 해당 문제는 인오더, 포스트오더 순회를 가지고 프리 오더 순회를 구하는 문제이다. 해당 문제는 포스트 오더의 마지막 값이 해당 순회의 root라는 점을 알아차려야 풀 수 있는 문제이다.

 

 root를 파악하고 이를 인 오더에 적용하여 작은 트리의 root 찾는 방식은 반복하면 된다.

 

 

다음과 같은 트리가 있을 때, 인오더와 포스트오더로 나타내면 아래와 같다.

InOrder : 4 - 2 - 5 - 1 - 6 - 3 - 7

PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1

 

포스트오더로 나열하면 가장 오른쪽에 있는 값은 트리의 루트가 된다.

포스트오더는 왼쪽 노드 - 오른쪽 노드 - 가운데 노드 순서대로 순회하기 때문이다.

PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1

 

인오더에서는 루트를 기준으로 왼쪽은 왼쪽 자식 트리, 오른쪽은 오른쪽 자식 트리이다.

인오더는 왼쪽 노드 - 가운데 노드 - 오른쪽 노드 순서대로 순회하기 때문이다.

InOrder : 4 - 2 - 5 - 1 - 6 - 3 - 7

 

 

정리하자면, 인오더와 포스트오더의 정보가 주어졌을 때,

포스트오더를 통해서는 트리의 루트를 알 수 있고, 인오더를 통해서는 왼쪽 자식 트리와 오른쪽 자식 트리를 알 수 있다.

 

이제 이렇게 얻은 정보로 프리오더의 순서를 알 수 있다.

프리오더는 가운데 노드 - 왼쪽 노드 - 오른쪽 노드 순서대로 순회한다.

따라서 포스트오더에서 가장 오른쪽에 있던 루트 노드가 프리오더에서는 가장 먼저 오게 된다.

 

PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1

PreOrder : 1 - ○ - ○ - ○ - ○ - ○ - ○

 

 

그렇다면 1 다음으로는 어떤 수가 와야 할까?

가운데 노드를 방문한 다음에는 왼쪽 자식 트리를 똑같은 방법으로 순회해야 한다.

마찬가지로 왼쪽 자식 트리의 루트 노드를 먼저 방문하고 그 다음 왼쪽 노드, 오른쪽 노드를 차례로 방문한다.

왼쪽 자식 노드에서는 2가 루트노드이므로 1 다음에는 2를 순회하게 된다.

마찬가지로 인오더에서 2를 기준으로 왼쪽에 있는 값들은 왼쪽 자식 노드, 오른쪽에 있는 값들은 오른쪽 자식 노드에 해당함을 알 수 있다.

 

PostOrder : 4 - 5 - 2 

PreOrder : 1 - 2 - ○ - ○ - ○ - ○ - ○

InOrder : 4 - 2 - 5

 

 

 

이런식으로 계속 포스트오더에서 트리 노드를 찾고, 인오더에서는 트리 노드를 기준으로 좌우로 나누어 왼쪽 자식 트리와 오른쪽 자식 트리를 찾는방식으로 프리오더의 순서를 채워넣으면 된다.

이렇게 분할하고 반복되는 과정은 재귀를 이용하게 손쉽게 구현할 수 있다.

 

그렇다면 언제까지 반복하는가?

트리에 노드가 하나밖에 없을때까지 반복한다. 즉, 더 이상 왼쪽 자식 트리와 오른쪽 자식 트리로 나눌 수 없을 때까지 반복한다.

---

풀이 코드

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.io.*;


public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static StringTokenizer st;
	public static StringBuilder sb = new StringBuilder();
	public static int INF = 100_000_000;

	public static ArrayList<Integer> preorder = new ArrayList<>();
	public static int[] inorder;
	public static int[] postorder;
	
	public static void main(String[] args) throws IOException{
		int N = Integer.parseInt(br.readLine());
		
		inorder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		postorder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		
		getPreorder(0,N-1,0,N-1);
		for(int i = 0 ; i < N;i++) {
			sb.append(preorder.get(i) + " ");
		}
		System.out.println(sb.toString());
	}
	
	public static void getPreorder(int inStart, int inEnd, int postStart, int postEnd) {
		if(inStart>inEnd || postStart > postEnd)return;
		
		int root = postorder[postEnd];
		int index = 0;
		for(int i = 0 ; i < inorder.length;i++) {
			if(root == inorder[i])index = i;
		}

		preorder.add(root);
		getPreorder(inStart, index - 1, postStart, postStart + index - inStart - 1);
		getPreorder(index + 1, inEnd, postStart + index - inStart, postEnd - 1);
		
	}
	
}

---

Reference

https://lotuslee.tistory.com/82