[백준] 2263번 트리의 순회

문제 설명

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

문제 풀이

• 트리에서 인오더, 프리오더, 포스트오더의 성질을 이용하여 풀이하였다.
• 인오더 순서의 특징은 루트 노드의 인덱스를 기준으로 왼쪽값들은 왼쪽 자식 트리, 오른쪽값들은 오른쪽 자식 트리가 된다.
• 포스트오더 순서의 특징은 마지막 인덱스의 노드가 루트노드가 된다.
• 주어진 배열에서 다음 함수와 같이 재귀를 이용하여 프리오더의 값을 출력한다.

  • preOrder(인오더 시작인덱스, 인오더 마지막 인덱스, 포스트오더 시작인덱스, 포스트오더 마지막인덱스)

    	0. 시작 인덱스 > 마지막 인덱스이면 재귀 종료 
    	1. root 노드 출력 (포스트오더 마지막인덱스 숫자)
    	2. 좌측 트리 출력 
    		- preOrder(인오더 시작인덱스, 인오더 배열에서 루트바로 왼쪽노드, 
    					포스트오더 시작인덱스, 인오더배열의 좌측 트리 크기만큼 포스트오더 시작인덱스에서 더해줌)
    	3. 우측 트리 출력
    		- preOrder(인오더배열 루트 바로 오른쪽 노드, 인오더 마지막 인덱스,
    					포스트오더 시작인덱스에서 인오더왼쪽트리크기만큼 더해줌, 포스트오더 마지막 인덱스 - 1) 

소스 코드 (JAVA)

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

class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;
    public static int N;
    public static int[] inOrder, postOrder;
    public static int[] index; //인오더 배열에서 특정 값의 인덱스 저장

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        inOrder = new int[N];
        postOrder = new int[N];
        index = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            inOrder[i] = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            postOrder[i] = Integer.parseInt(st.nextToken());
        for (int i = 0; i < N; i++)
            index[inOrder[i]] = i;
    }

    //루트 노드부터 postOrder의 마지막 부분을 따라가면서 출력
    public static void preOrder(int inOrderS, int inOrderE, int postOrderS, int postOrderE) throws IOException {
        if (inOrderS > inOrderE || postOrderS > postOrderE)
            return;

        //현재 분기에서 루드노드는 postOrder 배열의 마지막 노드
        int root = postOrder[postOrderE];
        bw.write(root + " ");

        //인오더 배열에서는 루트 노드의 좌측 배열이 왼쪽 자식
        //포스트오더 배열에서는 postOrderS부터 인오더 왼쪽 자식의 크기만큼이 왼쪽 자식
        preOrder(inOrderS, index[root] - 1, postOrderS, postOrderS + (index[root] - 1 - inOrderS));

        //인오더 배열에서는 루트 노드의 우측 배열이 오른쪽 자식
        //포스트오더 배열에서는 왼쪽 자식 크기 이후 부터 마지막 노드 -1까지 오른쪽 자식
        preOrder(index[root] + 1, inOrderE, postOrderS + index[root] - inOrderS, postOrderE - 1);
    }
    public static void main(String[] args) throws IOException {
        input();
        preOrder(0, N-1, 0, N-1);
        bw.flush();
    }
}