[SWEA] 7985 Rooted Binary Tree 재구성

문제 출처: swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWu1JmN6Js4DFASy

SW Expert Academy

: 어떤 이진 트리를 중위순회한 결과가 배열로 주어지고 원래 이진트리의 순서를 찾아 레벨별로 출력해야 한다.

 

1. 주어진 중위순회 결과를 처음부터 방문하는데 방문한 후 바로 왼쪽 자식과 오른쪽 자식을 방문하도록 재귀함수를 만든다.(왼쪽 자식은 부모노드의 번호X2, 오른쪽 자식은 부모노드의 번호X2+1을 번호로 갖는다.)

 

2. 이때 중위 순회이기 때문에 부모 노드는 항상 가운데에 있다. 따라서 start와 end를 통해 범위를 주고 그 중간에 있는 부모노드를 찾을 수 있도록 한다.

 

3. start와 end가 같아지는 것은 한 개의 노드 밖에 없다는 뜻이다. 즉, 자식노드가 더 이상 존재하지 않는 leaf 노드이기 때문에 또 다시 자식노드를 찾으러 가지 않도록 메소드를 return 시켜 준다.

 

4. start와 end가 0과 배열의 길이를 넘을 때에도 return 시켜 주고 number가 N보다 커진다는 것은 모든 노드를 다 거친 것이기 때문에 이 경우도 return 시켜 준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Solution {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int K, N;
    static int[] tree;
    public static void main(String[] args) throws NumberFormatException, IOException {
        int T = Integer.parseInt(br.readLine());
        for(int tc = 1; tc <= T; tc++) {
            K = Integer.parseInt(br.readLine());
            N = (int)Math.pow(2, K) -1;
            tree = new int[N];
            ans = new int[N];
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i < N; i++)
                tree[i] = Integer.parseInt(st.nextToken());
             
             
            search(0,N-1,1);
            sb.append("#" + tc + " ");
            cnt = 0;
            int i = 0;
             while(cnt < N){
                for(int j = 0; j < Math.pow(2, i); j++) {
                    sb.append(ans[cnt++]+" ");                  
                } 
                i++;
                sb.append("\n");
            }
        }
        System.out.println(sb);
    }
    static int[] ans;
    static int cnt;
    static void search(int start, int end, int number) {
        if(start < 0 || start > N || end > N || end < 0 || number > N) return;
         
        int idx = (start+end)/2;
        ans[number-1] = tree[idx]; 
        if(start == end) return;
        search(start, idx-1, 2*number);
        search(idx+1, end, 2*number+1);
    }
}