[백준 #2263] 트리의 순회

문제

#2263 트리의 순회

 

난이도 : Gold I

 

1부터 n까지 번호가 하나씩 새겨진 노드들로 이루어져 있는 이진 트리를 inorder(중위 순회)한 결과와 postorder(후위 순회)한 결과가 주어졌을 때, 그 이진 트리를 preorder(전위 순회)한 결과를 출력하면 된다.

 

 

아이디어

 

우선, 각각의 순회는 루트에서 시작해서 다음과 같은 순서로 노드를 재귀적으로 순회한다.

 

전위 순회 : 루트 - 왼쪽 서브트리 - 오른쪽 서브트리

중위 순회 : 왼쪽 서브트리 - 루트 - 오른쪽 서브트리

후위 순회 : 왼쪽 서브트리 - 오른쪽 서브트리 - 루트

 

즉, 후위 순회에서 항상 맨 마지막은 그 트리의 루트임이 보장되고, 중위 순회에서 이 루트가 등장하는 위치를 알고 있다면 그 위치를 기준으로 왼쪽 서브트리와 오른쪽 서브트리로 나눌 수 있는 것이다.

 

예를 들어, 다음과 같은 트리를 생각해 보자.

 

이 트리를 중위 순회한 결과는 [6, 3, 7, 2, 4, 5, 1, 8, 9] 이고, 후위 순회한 결과는 [6, 7, 3, 5, 4, 2, 9, 8, 1]이다.

 

 

 

각각의 서브트리에서 후위 순회의 맨 오른쪽이 항상 그 서브트리의 루트이다.

 

이렇게 각각의 서브트리에서 inorder와 postorder의 범위를 구하면 왼쪽 서브트리와 오른쪽 서브트리로 나눌 수 있고, 루트를 먼저 출력해준다면 전위 순회한 결과를 얻을 수 있을 것이다.

 

 

이때, 위치를 매번 선형 탐색을 하며 찾으려 한다면 꽤나 시간이 오래 걸릴 것이기 때문에, 중위 순회에서 각각의 노드가 등장하는 위치를 가지고 있는 배열을 따로 만들어주었다.

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    static int[] in, post, idx;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        in = new int[n]; post = new int[n]; idx = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            in[i] = Integer.parseInt(st.nextToken());
            idx[in[i]] = i;
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) post[i] = Integer.parseInt(st.nextToken());
        recursion(0, n - 1, 0, n - 1);
        bw.close();
    }

    private static void recursion(int inl, int inr, int postl, int postr) throws IOException {
        if(postl > postr) return;
        int index = idx[post[postr]];
        bw.write(in[index] + " ");
        recursion(inl, index - 1, postl, postr - inr + index - 1);
        recursion(index + 1, inr, postr - inr + index, postr - 1);
    }
}