[백준] 9934 - 완전 이진 트리

[문제링크]

9934번: 완전 이진 트리

 

0. 완전 이진 트리를 중위 순회한 결과가 주어졌을때, 원래의 트리를 복원하는 문제

 

1. 완전 이진 트리의 특성상, 왼쪽 subtree와 오른쪽 subtree의 크기가 동일하다

• 중위 순회는 왼쪽 - 자신 - 오른쪽 순서로 이루어지므로, 정 가운데 번호가 항상 root노드이다

 

2. 시작-끝 값으로 subtree 정보를 유지하면서, 가운데(root) 정보를 저장하며 재귀를 진행한다

• 재귀의 깊이에 따라 각 list에 저장
• subtree의 크기가 0이되면 종료한다

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = pint(br.readLine());
		int[] node = new int[(int)Math.pow(2, N)-1];
		ArrayList<LinkedList<Integer>> list = new ArrayList<>();
		for(int i=0; i<N; i++) {
			list.add(new LinkedList<>());
		}
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < node.length; i++) {
			node[i]=pint(st.nextToken());
		}
		
		rec(list, node, 0, node.length, 0);
		
		for(int i=0; i<N; i++) {
			for(Integer e : list.get(i)) {
				System.out.print(e+" ");
			}System.out.println();
		}
	}
	
	static void rec(ArrayList<LinkedList<Integer>> list, int[] node, 
			int fst, int lst, int depth) {
		
		if(fst==lst)return;
		int mid = (fst+lst)/2;
		
		list.get(depth).add(node[mid]);
		
		rec(list, node, fst, mid, depth+1);//left
		rec(list, node, mid+1, lst, depth+1);//right
	}
	
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면