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

핵심

이진검색트리가 무엇인지 이해하는 것이 중요했다.
이진검색트리는 아래의 3가지 조건을 만족하는 이진트리이다.

1. 노드왼쪽 서브트리의 모든노드의 키는 노드의 키보다 작다.
2. 노드오른쪽 서브트리의 모든노드의 키는 노드의 키보다 크다.
3. 왼쪽, 오른쪽 서브트리도 이진검색트리이다.

 

 

키워드

전위순회의 첫요소가 루트이다.
재귀호출 흐름을 '왼쪽서브트리, 오른쪽서브트리, 루트출력' 과 같이 만들면 후위순회의 순서대로 출력된다.

 

포인트

1️⃣ List<Integer>에 전위순회 입력값을 모두 담고 다시 배열에 옮긴다.
2️⃣ 재귀호출시 root 위치의 인덱스를 배열에서 찾아 출력한다. 

 

//1. 전위순회 결과값을 배열에 옮겨담는다.
//2. 주어진 전위순회의 시작인덱스 0 과 끝 인덱스를 시작인자로 
//   postorder 를 위한 재귀호출을 시작한다.
//3. 재귀호출시 종료조건을 설정하고, root의 위치 값은 시작인덱스 + 1로 설정한다.
//4. 만약 현재 설정한 위치값이 배열의 시작인덱스의 값보다 작다면(즉, 오른쪽서브트리 시작점이 루트보다 작다면)
//   while문을 사용해 idx++ 로 조건에 맞을때까지 idx를 증가시킨다.
//5. 그리고 왼쪽,오른쪽 순서로 재귀호출과 루트 출력을 순서대로 진행한다.
//6. 왼쪽서브트리 재귀호출시 시작인덱스와 끝인덱스의 범위는 '시작+1 ~ idx-1' 이다. 
//7. 오른쪽서브트리 재귀호출시 시작인덱스와 끝인덱스 범위는 'idx ~ 끝인덱스-1'이다.

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

public class Main{
    static int[] preorder;
    static int n;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<Integer> list = new ArrayList<>();
        String line;
        
        while((line = br.readLine()) != null && !line.isEmpty())
            list.add(Integer.parseInt(line));
        
        n = list.size();
        preorder = new int[n];
        for(int i = 0; i < n; i++)
            preorder[i] = list.get(i);
        
        getPostorder(0, n-1);
    }
    
    public static void getPostorder(int start, int end) {
        if(start > end) return;
        
        int idx = start + 1;
        while(idx <= end && preorder[idx] < preorder[start]) idx++;
        
        getPostorder(start + 1, idx - 1);
        getPostorder(idx, end);
        System.out.println(preorder[start]);
    }
}

 

 

 

 

---

기억하자 메소-드

✅  offerFirst(), offerLast() : 큐의 처음, 큐의 마지막에 원소 추가

✅  pollFirst(), pollLast() : 큐의 처음, 큐의 마지막 요소를 제거

 

✅   Map.getOrDefault(Object key, V defaultValue) 

key	찾을 키 값
defaultValue	키가 맵에 없을 경우 반환할 기본값
(예시) map.getOrDefault(c,0) + v	키 c가 맵에 없을경우 값을 0으로 설정하고 그게 아니라면 v를 더함