[백준/Java] 4256 : 트리

백준 4256번 '트리' 풀이입니다. 전위/중위 순회 결과로 후위 순회를 구하는 문제입니다. 전위 순회의 첫 원소가 루트이고, 중위 순회에서 루트 위치로 서브트리를 나눠 재귀 호출하면 됩니다. pos 배열로 중위 순회에서의 위치를 O(1)에 찾아 전체 O(N)에 해결했습니다. 각 순회 순서와 재귀 범위 설정이 헷갈렸습니다.

---

📌 문제 정보

• 번호: 4256
• 제목: 트리
• 난이도: Gold 2
• 분류: 트리, 재귀, 분할 정복

---

💡 접근 방식

전위 순회와 중위 순회 결과가 주어졌을 때, 트리를 직접 구성하지 않고도 재귀적으로 구간을 분할하여 후위 순회 결과를 출력했습니다.

• 전위 순회의 preorder[preL]이 현재 서브트리의 루트
• 중위 순회에서 루트 위치 기준으로 왼쪽/오른쪽 서브트리 분할
• pos[value] 배열로 중위 순회 위치를 O(1) 조회

---

💻 핵심 코드

static void findPostorder(int preL, int preR, int inL, int inR) {
    if (preL > preR || inL > inR) return;

    int root = preorder[preL];
    int rootIdx = pos[root];
    int leftSize = rootIdx - inL;

    findPostorder(preL + 1, preL + leftSize, inL, rootIdx - 1);
    findPostorder(preL + leftSize + 1, preR, rootIdx + 1, inR);

    sb.append(root).append(' ');
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

---

📄 전체 코드

package B4265;

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

public class Main {
    static int N;
    static int[] preorder, inorder, pos;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringTokenizer st;
        for (int t = 0; t < T; t++) {
            N = Integer.parseInt(br.readLine().trim());
            preorder = new int[N]; inorder = new int[N]; pos = new int[N + 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++) { inorder[i] = Integer.parseInt(st.nextToken()); pos[inorder[i]] = i; }
            findPostorder(0, N - 1, 0, N - 1);
            sb.append('\n');
        }
        System.out.print(sb);
    }

    static void findPostorder(int preL, int preR, int inL, int inR) {
        if (preL > preR || inL > inR) return;
        int root = preorder[preL];
        int rootIdx = pos[root];
        int leftSize = rootIdx - inL;
        findPostorder(preL + 1, preL + leftSize, inL, rootIdx - 1);
        findPostorder(preL + leftSize + 1, preR, rootIdx + 1, inR);
        sb.append(root).append(' ');
    }
}