트리 순회 순서 변경

풀이

이 문제는 얼핏 보기엔 까다로워 보이지만 재귀 호출을 이용하면 아주 간단하게 구현할 수 있습니다. 다음과 같은 형태의 $printPostOrder()$ 함수를 정의해봅시다.

$printPostOrder(preOrder[], inOrder[])$=트리의 전위 순회 순서 $preOrder[]$와 중위 순회 순서 $inOrder[]$가 주어질 때, 후위 순회 순서를 출력한다.

가장 먼저 깨달아야 하는 것은 주어진 트리의 루트는 전위 순회에서 가장 먼저 방문되므로 $preOrder[0]$이 루트의 번호라는 점입니다. 루트의 번호 $root$를 찾았으면 $inOrder[]$에서 $root$를 찾아 봅시다. 중위 순회 결과에서 루트보다 먼저 방문된 노드들은 왼쪽 서브트리에, 늦게 방문된 노드들은 오른쪽 서브트리에 있습니다. 따라서 $inOrder[]$에서 $root$가 어디 있는지 찾으면 각 서브트리의 크기 $L, R$을 알 수 있습니다. 그러고 나면 $preOrder[]$와 $inOrder[]$를 적절히 잘라 왼쪽 서브트리의 붕문 순서, 오른쪽 서브트리의 방문 순서로 나눌 수 있습니다. 따라서 각 서브트리를 후위 순회한 결과를 재귀 호출을 이용해 출력하고, 마지막으로 루트의 번호를 출력하면 됩니다.

구현

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

public class Main {

    public static int find(int[] arr, int value) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == value) return i;
        }
        return -1;
    }

    // 트리의 전위탐색 결과와 중위탐색 결과가 주어질 때 후위탐색 결과를 출력하낟.
    public static void printPostOrder(int[] preOrder, int[] inOrder) {
        // 트리에 포함된 노드위 수
        final int N = preOrder.length;
        // 기저 사례: 텅 빈 트리면 곧장 종료
        if (preOrder.length == 0) return;
        // 이 트리의 루트는 전위 탐색 결과로부터 곧장 알 수 있다.
        final int root = preOrder[0];
        // 이 트리의 왼쪽 서브트리의 크기는 중위 탐색 결과에서 루트의 위치를 찾아서 알 수 있다.
        final int L = find(inOrder, root);
        // 오른쪽 서브트리의 크기는 N에서 왼쪽 서브트리와 루트를 빼면 알 수 있다.
        final int R = N - 1 - L;
        // 왼쪽과 오른쪽 서브트리의 순회 결과를 출력
        printPostOrder(Arrays.copyOfRange(preOrder, 1, L + 1), Arrays.copyOfRange(inOrder, 0, L));
        printPostOrder(Arrays.copyOfRange(preOrder, L + 1, N), Arrays.copyOfRange(inOrder, L + 1, N));
        // 후위 순회이므로 루트를 가장 마지막에 출력한다.
        System.out.print(root + " ");
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        int[] preOrder, inOrder;
        for (int i = 0; i < testCase; i++) {
            int N = Integer.parseInt(br.readLine());
            String preOrderStr = br.readLine();
            String midOrderStr = br.readLine();
            StringTokenizer tokenizer = new StringTokenizer(preOrderStr);
            preOrder = new int[tokenizer.countTokens()];
            for (int j = 0; j < preOrder.length; j++) {
                preOrder[j] = Integer.parseInt(tokenizer.nextToken());
            }
            tokenizer = new StringTokenizer(midOrderStr);
            inOrder = new int[tokenizer.countTokens()];
            for (int j = 0; j < inOrder.length; j++) {
                inOrder[j] = Integer.parseInt(tokenizer.nextToken());
            }
            printPostOrder(preOrder, inOrder);
            System.out.println();
        }
    }
}

시간 복잡도 분석

$printPostOrder()$의 수행 시간을 지배하는 것은 선형 시간이 걸리는 $find()$와 $Arrays.copyOfRange()$ 함수의 호출입니다. 트리의 각 노드마다 $printPostOrder()$가 한 번씩 호출되므로 전체 시간 복잡도는 $O(n^2)$임을 알 수 있습니다.

회고

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)