[InOrder 와 PostOrder 로부터 PreOrder 구하기] 백준 2263 트리의 순회 (JAVA)

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

2263번: 트리의 순회

재귀는 항상 어려운 것 같다.. 🥺

 

위 문제는 조금 특이한데,

 

InOrder Traverse 와 PostOreder Traverse 가 주어졌을 때 PreOrder Traverse 를 출력하는 것이 요구 사항이다.

 

음..

 

일단 Tree 의 순회에서 기준이 되는 것은 Root 노드이다.

 

InOrder 와 PostOrder 는 주어지는데,

 

이로부터 Root 노드를 어떻게 찾을 수 있을까?

 

PostOrder 는 left - right - root 순으로 순회하므로 PostOrder 로 주어진 값들의 가장 마지막이 Root 노드임을 알 수 있다.

 

InOrder 는 left - root - right 순으로 순회한다.

 

그러면 PostOrder 을 통해 얻은 Root 노드의 값을 이용하여,

 

InOrder 순서 중에서 Root 노드를 몇 번째 방문하는 지 확인하면 (RootIdx)  

 

Left Subtree 와 Right Subtree 를 얻어낼 수 있다.

 

어떻게?

 

InOrder 배열의 0~RootIdx-1 까지 = Left Subtree 

 

InOrder 배열의 RootIdx ~ n-1 까지 = Right Subtree

 

그리고 각각의 Subtree 에 대해서 위 작업을 반복해주면 된다.

 

언제까지? (terminate condition)

 

더이상 방문할 수 있는 노드가 없을 때 까지!

 

이제 코드로 구현해보자.

 

함수의 매개변수는

 

현재 Depth 에서 InOrder 의 시작지점 : InLeft

현재 Depth 에서 InOrder 의 끝지점 : InRight

현재 Depth 에서 PostOrder 의 시작지점 : PostLeft

현재 Depth 에서 PostOrder 의 끝지점 : PostRight

static void printPreOrder(int inLeft, int inRight, int postLeft, int postRight) throws  IOException 

 그리고 terminate condition 은 더이상 탐색할 노드가 없을 때 종료한다.

if(inLeft > inRight || postLeft > postRight)
    return;

root 노드는 postOrder 배열의 가장 끝에 있는 값이다.

int root = postOrder[postRight];

위 root 노드를 이용하여 InOrder 에서 left subtree 와 Right subtree 를 분리하는 것이 1차적인 목적이다.

 

이를 위해서는 InOrder 에서 현재 Depth 에서의 root 노드를 몇 번째로 탐색하는 지 Index 를 알아내야 한다.

 

간단하게 Linear search 로 구현하였다.

int rootIdx = 0;
for(int i = inLeft; i<=inRight; i++){
    if(inOrder[i] == root){
        rootIdx = i;
    }
}

그리고 현재 Depth 에서 root 노드를 출력한다.

bw.write(inOrder[rootIdx]+" ");

이제 RootIdx 를 이용하여 LeftSubTree , RightSubTree 의 Size 를 계산할 수 있다.

 

left - root - right 순으로 탐색하는 InOrder 의 특성을 이용하면 되는데,

 

InOrder 에서 root 노드는 rootIdx 번째로 탐색하므로

 

leftSubTree 의 size 는 rootIdx - inLeft

rightSubTree 의 size 는 inRight - rootIdx 이다.

 

이제 각각의 서브트리에 대해서 재귀적으로 동일한 작업을 수행하자.

 

먼저 left SubTree 에 대해서 생각해보자.

 

inOrder 배열의 시작점은 동일할 것이다. 

inOrder 배열의 끝점은 Root 의 이전까지이다. (rootIdx-1)

PostOrder 배열의 시작점은 동일할 것이다.

PostOrder 배열의 끝점은 PostOrder 배열의 시작점에서 leftSubTree 의 size 만큼 더한 뒤 1 을 뺀 것이다. (0 - index)

     PostLeft + leftSubtreeSize 라고 하면 Root 노드를 포함하게 된다. 

printPreOrder(inLeft, rootIdx - 1, postLeft, postLeft + leftSubtreeSize - 1);

Right SubTree 에 대해서 생각해보면,

 

InOrder 배열의 시작점은 root 노드의 다음부터일 것이다.

InOrder 배열의 끝점은 InRight 로 동일할 것이다.

PostOrder 배열의 시작점은 postLeft 에서 leftsubTreeSize 를 더한 것이다.

postRight 는 Root 노드를제외한 PostRight - 1 까지 일 것이다.

printPreOrder(rootIdx + 1, inRight, postLeft + leftSubtreeSize, postRight - 1);

인덱싱이 되게 헷갈리는데(1을 빼야 할지 더해야 할지), 그림을 그려놓고 루트 노드를 포함하지 않도록 해야한다는 것을 생각하면 몇 번의 시행착오를 거쳐서 해결할 수 있을 것이다..! 😢

 

전체 코드는 아래와 같다.

import javax.lang.model.SourceVersion;
import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int[] inOrder;
    static int[] postOrder;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;

        n = Integer.parseInt(br.readLine());
        inOrder = new int[100001];
        postOrder = new int[100001];

        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            inOrder[i] = Integer.parseInt(stk.nextToken());
        }

        stk = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            postOrder[i] = Integer.parseInt(stk.nextToken());
        }

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

        bw.flush();
        bw.close();
    }
    static void printPreOrder(int inLeft, int inRight, int postLeft, int postRight) throws  IOException {
        if(inLeft > inRight || postLeft > postRight)
            return;
        int root = postOrder[postRight];
        int rootIdx = 0;
        for(int i = inLeft; i<=inRight; i++){
            if(inOrder[i] == root){
                rootIdx = i;
            }
        }
        bw.write(inOrder[rootIdx]+" ");

        int leftSubtreeSize = rootIdx - inLeft;

        printPreOrder(inLeft, rootIdx - 1, postLeft, postLeft + leftSubtreeSize - 1);
        printPreOrder(rootIdx + 1, inRight, postLeft + leftSubtreeSize, postRight - 1);
    }


}