[백준] 4256: 트리 - JAVA

in Algorithm on 트리

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

풀이

트리구조의 개념과 재귀를 물어보는 문제였다.

트리의 전위순회, 중위순회한 결과를 알려주고 후위순회한 결과를 찾아야한다.

전위순회: root -> left -> right

중위순회: left -> root -> right

후위순회: left -> right -> root

전위순회에서 맨 앞의 값이 후위순회에서의 맨 마지막 값이 된다.

전위순회의 맨 앞의 값을 중위순회에서 찾아 left그룹과 right그룹으로 나눠 재귀 탐색을 한다.

메모리: 157856KB

시간: 644ms

언어: Java 11

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            int n = Integer.parseInt(br.readLine());

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

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

            String ans = solve(0, n - 1, pre, 0, n - 1, in);

            sb.append(ans).append("\n");
        }

        System.out.println(sb);

    }

    private static String solve(int pre_left, int pre_right, int[] pre, int in_left, int in_right, int[] in) {
        String root = String.valueOf(pre[pre_left]) + " ";
        String left = "";
        String right = "";

        if (pre_left != pre_right) {
            int index = in_left;
            for (int i = in_left; i < in_right; i++) {
                if (in[i] == pre[pre_left]) {
                    index = i;
                    break;
                }
            }
            int len = index - in_left;

            if (index != in_left) {
                left = solve(pre_left + 1, pre_left + len, pre, in_left, index - 1, in);
            }

            if (index != in_right) {
                right = solve(pre_left + len + 1, pre_right, pre, index + 1, in_right, in);
            }
        }

        return left + right + root;
    }

}