[백준 JAVA] 5639번: 이진 검색 트리

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

 

이진 검색 트리 문제는 처음 보면 트리를 직접 만들어야 할 것 같지만 실제로는 배열만으로 해결할 수 있는 문제다. 입력으로 주어지는 값은 트리의 전위 순회 결과이며 이를 이용해 후위 순회를 출력해야 한다.

 

전위 순회의 특징은 항상 첫 번째 값이 루트라는 점이다. 이 문제의 핵심은 이 성질과 이진 검색 트리의 규칙을 함께 사용하는 것이다. 이진 검색 트리는 루트보다 작은 값은 왼쪽 서브트리로 들어가고 큰 값은 오른쪽 서브트리로 들어간다.

 

전위 순회 배열을 보면 첫 번째 값은 루트이고 그 다음 값들 중에서 루트보다 작은 값들은 모두 왼쪽 서브트리에 해당한다. 그리고 어느 순간 루트보다 큰 값이 처음 등장하는데 그 지점부터는 모두 오른쪽 서브트리에 해당한다.

 

코드

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

public class Main {
    static List<Integer> pre = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String line;
        while ((line = br.readLine()) != null) {
            if (line.isEmpty()) break;

            pre.add(Integer.parseInt(line));
        }

        postOrder(0, pre.size() - 1);

        System.out.println(sb);
    }

    private static void postOrder(int start, int end) {
        if (start > end) return;
        int root = pre.get(start);
        int tmp = end + 1;
        for (int i = start + 1; i <= end; i++) {
            if (pre.get(i) > root) {
                tmp = i;
                break;
            }
        }
        postOrder(start + 1, tmp - 1);
        postOrder(tmp, end);
        sb.append(root).append('\n');
    }
}

이 문제를 풀면서 중요한 포인트는 트리를 직접 만들지 않아도 된다는 점이었다. 전위 순회 배열만으로도 충분히 서브트리를 구분할 수 있고 이를 이용해 재귀적으로 해결할 수 있다.

 

또 하나 중요한 점은 구간을 나누는 기준을 정확하게 이해하는 것이다. 루트를 기준으로 왼쪽과 오른쪽을 나누는 순간 재귀 구조가 자연스럽게 만들어진다. 이 방식은 다른 트리 문제에서도 자주 등장하기 때문에 한 번 제대로 이해해두면 이후 문제 풀이에 큰 도움이 된다.