[백준] 2263번 - 트리의 순회 (Gold 2)

문제 링크

백준 2263번 - 트리의 순회 (Gold 2)

문제 설명

이진트리의 중위순회(inorder)와 후위순회(postorder)가 주어져있다.
이 이진트리의 전위순회(preorder)를 구하시오.

정답 코드 및 설명

이진트리의 순회 방식은 백준 1991번 - 트리의 순회 (Silver 1)를 참고하면 된다.
여기서 중요한 사실은 다음 세가지이다.

• 루트 노드는 후위순회의 맨 끝 값이다.
• 왼쪽 자식은 중위순회에서 루트 노드의 왼쪽에 있는 값들이다.
• 오른쪽 자식은 중위순회에서 루트 노드의 오른쪽에 있는 값들이다.

이를 활용하여 재귀적으로 코드를 짜면 아래와 같다.

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

public class BOJ2263 {

    static int[] inorder, postorder, inorderIndex;
    static StringBuilder sb = new StringBuilder();

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        inorder = new int[n];
        postorder = new int[n];
        inorderIndex = new int[n + 1];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            inorder[i] = Integer.parseInt(st1.nextToken());
            postorder[i] = Integer.parseInt(st2.nextToken());
            inorderIndex[inorder[i]] = i;
        }
        preorder(0, n, 0, n);
        bw.write(sb.toString());
        bw.close();
    }

    static void preorder(int inStart, int inEnd, int postStart, int postEnd) {
        int n = postEnd - postStart;
        // 0개면 null tree -> 출력 없음
        if (n == 0)
            return;

        // 원소가 있으면 head 원소는 postorder의 맨 끝
        int head = postorder[postEnd - 1];
        int headIndex = inorderIndex[head];
        int leftLength = headIndex - inStart;

        // 출력
        sb.append(head).append(' ');
        preorder(inStart, headIndex, postStart, postStart + leftLength); // 왼쪽 자식
        preorder(headIndex + 1, inEnd, postStart + leftLength, postEnd - 1); // 오른쪽 자식
        return;
    }
}