b2263. 트리의 순회

 

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

 

 

 

📌 자바(Java)로 푸는 트리의 순회 - 백준 2263 🌲

 

Inorder + Postorder → Preorder 복원하기

 

🔎 문제 개요

 

백준 2263 - 트리의 순회 문제는,

 

• 이진 트리의 Inorder(중위 순회) 와 Postorder(후위 순회) 결과가 주어질 때,
• 이진 트리의 Preorder(전위 순회) 결과를 출력하는 문제입니다.

---

💡 예제 입력

3
2 1 3
2 3 1

 

💡 예제 출력

1 2 3

 

 

---

🛠 알고리즘 접근 방식

 

이 문제는 트리를 직접 복원하지 않고,

✔ 순회 결과만을 이용해 바로 Preorder를 만들어내는 것이 핵심입니다.

 

---

📌 트리 순회의 특징 이해하기

순회 방법순서

Preorder(전위 순회)	루트 → 왼쪽 → 오른쪽
Inorder(중위 순회)	왼쪽 → 루트 → 오른쪽
Postorder(후위 순회)	왼쪽 → 오른쪽 → 루트

 

📌 핵심 아이디어

 

• Postorder의 마지막 원소가 현재 서브트리의 루트다.
• 그 루트를 Inorder에서 찾으면,
  • 왼쪽 서브트리와 오른쪽 서브트리의 범위를 나눌 수 있다.
• Preorder에서는 루트 → 왼쪽 → 오른쪽 순으로 출력하면 된다.

 

📌 Java 코드 설명

 

1. 입력 및 초기화

N = Integer.parseInt(br.readLine());
inOrder = new int[N+1];
postOrder = new int[N+1];

StringTokenizer st1 = new StringTokenizer(br.readLine());
StringTokenizer st2 = new StringTokenizer(br.readLine());

✔ inOrder, postOrder를 각각 입력받는다.

 

✔ index 배열을 사용해서 inOrder 값의 인덱스를 빠르게 찾을 수 있게 준비한다.

index = new int[N+1];
for (int i = 1; i <= N; i++) {
    index[inOrder[i]] = i;
}

 

 

 

2. 핵심 재귀 함수 

solve()

static void solve(int is, int ie, int ps, int pe) {
    if (ie < is || pe < ps) return;
    
    int root = postOrder[pe]; // 후위 순회 끝값 = 현재 서브트리 루트
    int rIdx = index[root];   // 중위 순회에서 루트 위치 찾기
    sb.append(root + " ");    // 전위 순회는 루트를 먼저 출력

    int len = rIdx - is; // 왼쪽 서브트리 길이 계산

    // 왼쪽 서브트리 재귀
    solve(is, rIdx - 1, ps, ps + len - 1);

    // 오른쪽 서브트리 재귀
    solve(rIdx + 1, ie, ps + len, pe - 1);
}

✔ is, ie: 현재 Inorder 범위

✔ ps, pe: 현재 Postorder 범위

 

✔ 루트를 먼저 찍고 (Preorder)

✔ 왼쪽 트리 → 오른쪽 트리 순서로 재귀 호출한다.

 

 

3. 출력

System.out.println(sb);

✔ 결과는 StringBuilder로 저장해서 한 번에 출력한다.

 

---

✅ 정리

핵심 포인트	설명
Postorder 마지막 원소 → 현재 서브트리 루트	루트 기준으로 Inorder를 나눠야 함
Inorder에서 루트 위치를 찾고	왼쪽/오른쪽 서브트리 범위를 계산
Preorder는 루트를 먼저 출력	그다음 왼쪽 → 오른쪽 순서 재귀

 

---

🔥 코드 전체 (정리)

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

public class b2263 {
    static int N;
    static int[] inOrder, postOrder, index;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        inOrder = new int[N+1];
        postOrder = new int[N+1];

        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        for (int i = 1; i <= N; i++) {
            inOrder[i] = Integer.parseInt(st1.nextToken());
        }
        for (int i = 1; i <= N; i++) {
            postOrder[i] = Integer.parseInt(st2.nextToken());
        }

        index = new int[N+1];
        for (int i = 1; i <= N; i++) {
            index[inOrder[i]] = i;
        }

        sb = new StringBuilder();
        solve(1, N, 1, N);
        System.out.println(sb);
    }

    static void solve(int is, int ie, int ps, int pe) {
        if (ie < is || pe < ps) return;
        
        int root = postOrder[pe];
        int rIdx = index[root];
        sb.append(root).append(" ");

        int len = rIdx - is;
        solve(is, rIdx - 1, ps, ps + len - 1);
        solve(rIdx + 1, ie, ps + len, pe - 1);
    }
}