[백준] 5639- 이진 검색 트리 문제 풀이(자바,Java)

문제

5639번: 이진 검색 트리

들어가며

재귀적으로 접근해야겠다고 생각은 했는데

너무 어렵게 생각해서 오른쪽 서브 트리 처리에서 막혔었다.

하지만, 단순하게 보면 풀 수 있는 길이 있었다.

 

코드

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class 이진검색트리_5639 {
    static List<Integer> numbers = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNextLine()) {
            String input = scanner.nextLine();
            if (input.isEmpty()) {
                break;
            }
            int number = Integer.parseInt(input);
            numbers.add(number);
        }
        int n = numbers.size();

        search(0, n-1);
    }

    public static void search(int startIndex, int endIndex){
        if (startIndex>endIndex){
            return;
        }
        int root = numbers.get(startIndex);
        int rootRightChildIndex = startIndex+1;
        while (rootRightChildIndex <= endIndex && root > numbers.get(rootRightChildIndex)){
            rootRightChildIndex++;
        }

        search(startIndex+1,rootRightChildIndex-1);
        search(rootRightChildIndex,endIndex);
        System.out.println(numbers.get(startIndex));
    }

}

풀이

포인트는 바로 시작점에서부터 오른쪽으로 가면서 큰 값을 찾는 것이다.

그러면 그 큰 값은 오른쪽 자식임을 알 수가 있는데

그 이전의 수열들은 왼쪽 자식들인 것이다.

그래서 오른쪽 자식 기준으로 왼쪽과 오른쪽 서브트리를 분할하며 재귀를 실행하면 풀 수 있게 된다.

 

public static void search(int startIndex, int endIndex){
    if (startIndex>endIndex){
        return;
    }
    int root = numbers.get(startIndex);
    int rootRightChildIndex = startIndex+1;
    while (rootRightChildIndex <= endIndex && root > numbers.get(rootRightChildIndex)){
        rootRightChildIndex++;
    }

    search(startIndex+1,rootRightChildIndex-1);
    search(rootRightChildIndex,endIndex);
    System.out.println(numbers.get(startIndex));
}

다음 자식들을 계속 탐색할 수 있기에 기존 트리에서 후위 순회를 출력하는 방식처럼 출력하면 그만이다.