[백준] 2263번 : 트리의 순회 Gold1(골드1) - JAVA[자바]

[Gold I] 트리의 순회 - 2263

문제 링크

성능 요약

메모리: 62368 KB, 시간: 1280 ms

분류

분할 정복, 재귀, 트리

제출 일자

2024년 1월 23일 00:39:00

문제 설명

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

입력

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

출력

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

 

접근 방법

1. PostOrder(LRV)는 루트 노드가 가장 오른쪽에 위치한다. -> 트리의 루트를 알 수 있다.

2. InOrder(LVR)는 루트 노드를 기점으로 왼쪽 자식과 오른쪽 자식트리를 알 수 있다.

 

PreOrder(VLR) -> 현재 루트를 출력 후 왼쪽 집합, 오른쪽 집합순으로 출력한다.

1. 먼저 루트를 가질 수 있음 -> 포스트오더에서 루트를 알아낸다.

2. 인오더에서 포스트오더에서 구한 루트의 위치를 알아낸다.

3. 찾는다면 루트를 기준으로 왼쪽 : start부터 루트 -1 까지 오른쪽: 루트 + 1 end까지 다시 재귀함수를 호출한다.

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

public class Main {
    static StringBuilder sb;
    static int[] in, post;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        in = new int[n];
        post = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            in[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            post[i] = Integer.parseInt(st.nextToken());
        }
        preOrder(0, n - 1, 0, n - 1);
        System.out.println(sb);
    }
    // is = inOrderStart, ie = inOrderEnd, ps = postOrderStart, pe = postOrderEnd
    private static void preOrder(int is, int ie, int ps, int pe) {
        if(is > ie || ps > pe){
            return;
        }
        sb.append(post[pe]).append(" ");

        int rootIdx = 0;
        for (int i = is; i <= ie; i++) {
            // 인오더에서 루트 노드를 찾는다. -> 포스트오더의 마지막은 현 시점의 루트 노드인 걸 알 수 있음
            if (in[i] == post[pe]) {
                rootIdx = i;
                break;
            }
        }
        // 인오더에서 구한 루트를 기준으로 왼쪽과 오른쪽을 나눌 수 있다.
        // 왼쪽 집합 호출
        preOrder(is, rootIdx - 1, ps, ps + rootIdx - is - 1);
        // 오른쪽 집합 호출
        preOrder(rootIdx + 1, ie, ps + rootIdx - is, pe - 1);
    }
}