[BaekJoon] 4256 트리 (Java)

1.  문제 링크

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

2.  문제

요약

• 이진 트리의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있습니다.
• 이진 트리를 전위 순회, 중위 순회한 결과가 주어질 때, 두 순회한 결과를 가지고 다시 이진 트리를 만들 수 있습니다.
• 이진 트리의 전위, 중위 순회한 결과가 주어졌을 때, 후위 순회했을 때의 결과를 구하는 문제입니다.
• 입력: 첫 번째 줄에 테스트 케이스의 개수 T가 주어지고 각 테스트 케이스의 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 노드의 개수 n이 주어집니다. 테스트 케이스의 두 번째 줄에 이진 트리를 전위 순회한 결과가, 테스트 케이스의 세 번째 줄에 이진 트리를 중위 순회한 결과가 주어집니다.
  • 이진 트리의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있습니다.
  • 항상 두 순회 결과로 유일한 이진 트리가 만들어지는 경우만 입력으로 주어집니다.
• 출력: 각 테스트 케이스마다 후위 순회한 결과를 출력합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static Reader scanner = new Reader();
    static int n;
    static int[] preOrder, inOrder;

    static void input() {
        n = scanner.nextInt();
        preOrder = new int[n];
        inOrder = new int[n];

        for(int node = 0; node < n; node++)
            preOrder[node] = scanner.nextInt();

        for(int node = 0; node < n; node++)
            inOrder[node] = scanner.nextInt();
    }

    static void solution() {
        getPostOrder(0, 0, n - 1);
        sb.append('\n');
    }

    static void getPostOrder(int rootIdx, int start, int end) {
        if(rootIdx >= n) return;

        int root = preOrder[rootIdx];

        for(int idx = start; idx <= end; idx++) {
            if(root == inOrder[idx]) {
                getPostOrder(rootIdx + 1, start, idx);
                getPostOrder(rootIdx + 1 + idx - start, idx + 1, end);
                sb.append(root + " ");
            }
        }
    }

    public static void main(String[] args) {
        int T = scanner.nextInt();

        while(T-- > 0) {
            input();
            solution();
        }

        System.out.println(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 전위 순회는 루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회를 진행하고 중위 순회는 왼쪽 서브 트리 -> 루트 -> 오른쪽 서브 트리 순으로 순회를 진행합니다.
• 중위 순회가 위처럼 순회를 진행하기 때문에 트리의 루트 노드를 안다면 루트 노드를 기준으로 왼쪽 노드들은 왼쪽 서브 트리가, 오른쪽 노드들은 오른쪽 서브 트리가 될 것입니다.
• 전위 순회를 이용하여 각 서브 트리의 루트 노드를 알 수 있습니다.
  • 전위 순회의 첫 노드가 전체 트리의 루트 노드이기 때문에 이를 적용해 중위 순회에서 왼쪽 서브 트리와 오른쪽 서브 트리를 구합니다.
  • 이후에는 왼쪽 서브 트리에 대해서는 전위 순회의 노드를 앞에서부터 하나씩, 오른쪽 서브 트리에 대해서는 적절한 위치를 찾아 해당 노드를 루트로 하여 왼쪽 서브 트리, 오른쪽 서브 트리를 계속해서 구해나가면서 후위 순회 결과를 찾습니다.