백준 5639 이진 검색 트리 Java [트리 순회]

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

5639번: 이진 검색 트리

예제를 배열로 만들면 [50, 30, 24, 5, 28, 45, 98, 52, 60]이 된다

50이 루트 노드이고 왼쪽 자식 노드는 30, 오른쪽 자식 노드는 98이다

30부터 98의 전인 45까지가 왼쪽 자손이고, 98부터 오른쪽 자손이다

이 규칙을 이용해 분할 정복으로 풀이하면 된다

먼저 루트는 50이고 배열을 탐색해서 50보다 큰 숫자를 만나면

해당 인덱스를 기준으로 아래와 같이 나눠서 재귀로 계속 나누고 리프노드일때 출력하면 된다

postOrder(left, index-1)

postOrder(index, right)

 

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Integer> arrayList = new ArrayList<>();
        arrayList.add(Integer.parseInt(br.readLine()));
        while (br.ready()) {
            arrayList.add(Integer.parseInt(br.readLine()));
        }
        arr = arrayList.stream().mapToInt(Integer::intValue).toArray();
        postOrder(0, arrayList.size()-1);
        System.out.println(sb);
    }
    static void postOrder(int left, int right) {
        if (left > right) return;
        int idx = -1;
        for (int i = left + 1; i <= right; i++) {
            if (arr[i] > arr[left]) {
                idx = i;
                break;
            }
        }
        if (idx == -1) idx = right+1;
        postOrder(left+1, idx - 1);
        postOrder(idx, right);
        sb.append(arr[left]).append("\n");
    }
}

주의할점

- 입력이 몇 줄인지 나와있지않기 때문에 BufferedReader의 ready 메서드를 사용해서 다음 값이 있는지 확인해야함

- ready() 메서드 사용하기전에 readLine 안하면 입력을 받지 않았다

- ready 메서드를 사용하지않고 readLine이 null인지 확인해서 null이 아닌 경우 ArrayList에 추가하도록 할 수 있다