P.2263 트리의 순회

코드

import java.io.*;
import java.util.Arrays;

public class P_2263 {

    static BufferedWriter bw;
    static int[] inOrder, postOrder;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        inOrder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        postOrder = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int root = postOrder[n - 1];
        int leftStart = 0, leftEnd = 0, rightStart = 0, rightEnd = n - 1;
        for (int i = 0; i < n; i++) {
            if (inOrder[i] == root) {
                bw.write(root + " ");
                if (i != 0) findTree(i, 0, i - 1, 0, i - 1);
                if (n - i - 1 != 0) findTree(n - i - 1, i + 1, n - 1, i, n - 2);
                break;
            }
        }

        bw.flush();
    }

    private static void findTree(int length, int inStart, int inEnd, int poStart, int poEnd) throws IOException {
        int root = postOrder[poEnd];
        bw.write(root + " ");

        if (length == 1) return ;

        int subLen = 0;
        for (int i = inStart; i <= inEnd; i++) {
            if (inOrder[i] == root) {
                if (subLen != 0) findTree(subLen, inStart, inStart + subLen - 1, poStart, poStart + subLen - 1);
                if (length - subLen - 1 != 0) findTree(length - subLen - 1, inStart + subLen + 1, inEnd, poStart + subLen, poEnd - 1);
                break;
            }
            subLen++;
        }
    }
}

코드 설명

서브트리 혹은 트리의 루트는 항상 postOrder의 마지막에 온다.

이를 기점으로 왼쪽, 오른쪽 서브트리로 생각할 수 있다.

 

왼쪽 서브트리의 루트는 또 왼쪽 서브트리 postOrder의 마지막 원소이고,

오른쪽 서브트리의 루트는 또 오른쪽 서브트리 postOrder의 마지막 원소가 된다.

또, 이 루트를 기점으로 서브트리의 서브트리를 재귀로 넘겨주면 된다.

 

처음에는 왼쪽, 오른쪽 서브트리의 inOrder, postOrder를 배열로 만들어서 넘겨주었는데 메모리 초과가 발생해서 인덱스만 넘겨주는 것으로 변경했다.

인덱스를 찾는게 꽤 시간이 오래 걸려서 직접 그려보면서 찾는 게 좋은 것 같다.