[백준 #2263] 트리의 순회 - JAVA [자바]

분류

분할 정복, 재귀, 트리

 

문제 설명

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

 

입력

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

 

출력

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

 

예제 입력

3
1 2 3
1 3 2

 

예제 출력

2 1 3

 

코드 - 트리의 순회.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    static int[] inOrder, postOrder, inOrderIndex; // 인오더, 포스트오더 및 인오더 인덱스를 저장할 배열 선언

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine()); // 정점의 개수 n 입력 받음

        inOrder = new int[n];
        postOrder = new int[n];
        inOrderIndex = new int[n + 1];

        // 인오더 입력 및 인덱스 정보 저장
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            inOrder[i] = Integer.parseInt(st.nextToken());
            inOrderIndex[inOrder[i]] = i; // 해당 값의 인오더 인덱스 정보 저장
        }

        // 포스트오더 입력
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) {
            postOrder[i] = Integer.parseInt(st.nextToken());
        }

        // 프리오더를 계산하고 출력하는 함수 호출
        solve(0, n - 1, 0, n - 1);
    }

    // 프리오더를 계산하고 출력하는 함수
    public static void solve(int inOrderStart, int inOrderEnd, int postOrderStart, int postOrderEnd) {
        if (inOrderStart > inOrderEnd || postOrderStart > postOrderEnd) { // 종료 조건
            return;
        }

        int root = postOrder[postOrderEnd]; // 포스트오더의 마지막 요소는 항상 루트이다
        System.out.print(root + " "); // 루트를 출력
        int rootIndex = inOrderIndex[root]; // 루트의 인오더 인덱스를 찾음

        int leftSize = rootIndex - inOrderStart; // 왼쪽 서브트리의 크기 계산

        // 왼쪽 서브트리에 대해 재귀 호출
        solve(inOrderStart, rootIndex - 1, postOrderStart, postOrderStart + leftSize - 1);
        // 오른쪽 서브트리에 대해 재귀 호출
        solve(rootIndex + 1, inOrderEnd, postOrderStart + leftSize, postOrderEnd - 1);
    }
}

 

코드 분석하기

1. 정점의 개수(n)를 입력 받고, 인오더와 포스트오더를 저장할 배열을 초기화합니다.
2. 인오더를 입력 받고, 각 정점의 인덱스를 찾아 inOrderIndex 배열에 저장합니다.
3. 포스트오더를 입력 받습니다.
4. solve 함수를 호출하여 프리오더를 계산하고 출력합니다.

solve 함수는 재귀적으로 호출되며, 각 호출은 다음과 같은 작업을 수행합니다:

1. 종료 조건 확인: inOrderStart > inOrderEnd 또는 postOrderStart > postOrderEnd인 경우, 현재 범위에 노드가 없으므로 함수를 종료합니다.
2. 루트 노드 출력: 포스트오더의 마지막 요소는 항상 루트 노드입니다. 루트 노드를 출력합니다.
3. 루트 노드의 인오더 인덱스를 사용하여 왼쪽 서브트리와 오른쪽 서브트리를 구분합니다.
4. 왼쪽 서브트리에 대해 solve 함수를 재귀적으로 호출합니다. 이 때 인오더와 포스트오더의 범위를 왼쪽 서브트리로 제한합니다.
5. 오른쪽 서브트리에 대해 solve 함수를 재귀적으로 호출합니다. 이 때 인오더와 포스트오더의 범위를 오른쪽 서브트리로 제한합니다.

이 과정을 통해 주어진 인오더와 포스트오더에 대한 프리오더를 계산하고 출력할 수 있습니다. 이 방식은 분할 정복 알고리즘의 원칙을 따르며, 이진 트리의 특성을 활용하여 문제를 해결합니다.

 

 

백준에서 문제 풀어보기

 

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

2263번: 트리의 순회