백준 9934

처음 보는 유형이었다.

 

이분 트리 유형으로 <중위순회> 라는 움직임을 알면 쉽다고 한다.

 

중위순회 움직임에 대해서 살짝 서칭한 후 구현하였다.

 

처음에 int[] 로 답을 출력하니 숫자가 들어갈때마다 초기화된다는 것을 깜빡했다.

 

그래서 String[ ] 로 바꿔서 문장형태로 출력했다.

 

또 하나의 방법을 알았다.

public class Baekjoon9934 {
    static int k;
    static String[] result;
    static int[] arr;
    static void root(int s, int e, int floor){
        if(floor==k)
            return;

        int m = (s+e)/2;
        result[floor] += Integer.toString(arr[m])+" ";
//        System.out.print(" m = " + m);
//        System.out.print(" floor = " + floor);
//        System.out.println(" result["+floor+"] = " + result[floor]);
        
        root(s, m-1, floor+1);
        root(m+1, e, floor+1);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        k = Integer.parseInt(br.readLine());
        result = new String[k];
        int n = (int) Math.pow(2, k);
        arr = new int[n-1];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n-1; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for(int i=0; i<result.length; i++){
            result[i]="";
        }
        root(0,arr.length,0);

        for(int i=0; i<result.length; i++){
            System.out.println(result[i]);
        }
    }
}