[백준] 5639 - 이진 검색 트리

[문제링크]

5639번: 이진 검색 트리

 

0. bufferedreader로 EOF 입력받는법 : null인지 아닌지 체크하기

 

1. 모든 수를 입력받아서 list로 저장

 

2. 전위순회의 결과물이므로 [루트] [왼쪽 서브트리] [오른쪽 서브트리] 의 형태로 나눌 수 있다.

 

3. 루트보다 커지는 지점이 오른쪽 서브트리의 시작점이므로, [왼쪽 서브트리] > [오른쪽 서브트리] > [루트] 의 순서로 재귀를 실행한다

 

4. 인자로 받은 서브트리가 1칸짜리면 그 원소를 list에 넣고 반환한다

  - 루트는 1칸짜리라 재귀 실행 = list에 자신 저장이므로 재귀 호출 대신 직접 넣는다

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String s;
		num = new ArrayList<>();
		back = new ArrayList<>();
		
		while((s=br.readLine())!=null) {
			num.add(pint(s));
		}
		
		rec(0,num.size()-1);
		
		for (int i = 0; i < back.size(); i++) {
			System.out.println(back.get(i));
		}
		
	}
	static ArrayList<Integer>num;
	static ArrayList<Integer>back;
	
	static void rec(int s, int e) {
		if(s==e) {
			back.add(num.get(s));
			return;
		}
		
		int root = num.get(s);
		int cnt=s+1;
		while(cnt<=e && num.get(cnt)<root)cnt++;
		
		if(s+1<=cnt-1)rec(s+1, cnt-1);
		if(cnt<=e)rec(cnt,e);
		back.add(root);
	}
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면