[백준 4256] 트리 (JAVA)

문제

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

풀이

전위 순회를 통해 root를 파악 후 중위 순회 왼쪽에 있는지 오른쪽에 있는지 범위를 좁히며 위치를 파악합니다. 만약에 양쪽에 없으면 부모 노드로 올라가 탐색합니다.

1) root를 찾습니다.
전위 순회 : 3 6 5 4 8 7 1 2
중위 순회 : (5 6 8 4 3 1 2 7)

2) 다음은 6, 중위 순회에서 왼쪽입니다.
전위 순회 : 3 6 5 4 8 7 1 2
중위 순회 : (5 6 8 4) 3 1 2 7

3) 다음은 5 중위 순회에서 왼쪽입니다.
전위 순회 : 3 6 5 4 8 7 1 2
중위 순회 : (5) 6 8 4 3 1 2 7

4) 다음은 4 중위 순회에서 5기준 좌우에 없으므로 출력 후 올라갑니다.
전위 순회 : 3 6 5 4 8 7 1 2
중위 순회 : (5 6 8 4) 3 1 2 7

5) 6의 오른쪽에 있습니다.

6) 계속 반복합니다.

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    static int n, idx;
    static int[] preorder, inorder, index;
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());
            preorder = new int[n];
            inorder = new int[n];
            index = new int[n + 1];
            idx = 1;
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < n; i++) {
                preorder[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < n; i++) {
                int num = Integer.parseInt(st.nextToken());
                inorder[i] = num;
                index[num] = i;
            }

            find(preorder[0], -1, preorder.length);
            bw.write("\n");
        }

        bw.close();
        br.close();
    }

    public static void find(int num, int left, int right) throws IOException {

        if (idx < n) {
            int node = preorder[idx];

            if (left < index[node] && index[node] < index[num]) {
                idx++;
                find(node, left, index[num]);
            }
        }

        if (idx < n) {
            int node = preorder[idx];

            if (index[num] < index[node] && index[node] < right) {
                idx++;
                find(node, index[num], right);
            }
        }

        bw.write(num + " ");
    }
}