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

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

2263번: 트리의 순회

문제 풀이

중위, 후위 순회의 탐색 순서가 주어졌을 때 전위 순회의 탐색 순서를 출력하는 문제이다.

이 문제를 해결하기 위해선 각 순회 탐색의 특징을 먼저 알아야 한다,.

우선 특징을 이해하기 위해선 중위 전위 후위 순회의 탐색 순서를 먼저 알아야 한다.

각 순회의 탐색 순서가 위와 같을 때 다음과 같은 특징을 가진다.

post order(후위)의 마지막은 루트 노드이고
in order(중위)에서는 루트 노드를 기준으로 왼쪽은 왼쪽 서브 트리, 오른쪽은 오른쪽 서브 트리로 나뉘어짐을 알 수 있다.

그렇다면 pre order(중위)의 탐색 순서는 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 임을 알고 있다. 따라서 post order로 루트 노드를 찾고 in order에서 해당 루트 노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리를 찾아 위 과정을 재귀를 진행시킬 수 있을 것이다.

 

아래와 같은 트리를 예시로 살펴보자.

 

 

post order에서 루트 노드를 찾고 in order에서 해당 루트 노드를 기준으로 왼쪽, 오른쪽 서브트리를 재귀 호출하는 과정임을 생각하고 그림을 참고하면 이해하기 쉬울 것이다. 

또한 pre oder (루트 -> 왼쪽 -> 오른쪽)을 구하는 과정이기 때문에 2를 루트로 가지는 서브트리에서 왼쪽 서브트리를 다 마치고 오른쪽을 탐색하기 때문에 5가 8, 9보다 늦게 탐색됨에 주의하자.

 

코드

package 백준;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class b2263 {

    static int n;
    static int[] inorder, postorder, preorder;
    static int preIdx;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());

        inorder = new int[n];
        postorder = new int[n];
        preorder = new int[n];

        inorder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        postorder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        getPreOrder(0, n - 1, 0, n - 1);

        Arrays.stream(preorder).forEach(i -> sb.append(i + " "));
        System.out.println(sb);
    }

    public static void getPreOrder(int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd)
            return;

        // 1. 루트 노드 탐색
        preorder[preIdx++] = postorder[postEnd]; // 포스트 오더의 가장 오른쪽은(post[postEnd]) 루트 노드이다.

        int pos = inStart;
        for (int i = inStart; i <= inEnd; i++) { // 인오더에서 루트 노드의 위치를 찾음
            if (inorder[i] == postorder[postEnd]) {
                pos = i;
                break;
            }
        }

        // 2. 왼쪽 서브트리 탐색
        getPreOrder(inStart, pos - 1, postStart, postStart + pos - inStart - 1);

        // 3. 오른쪽 서브트리 탐색
        getPreOrder(pos + 1, inEnd, postStart + pos - inStart, postEnd - 1);
    }
}