[백준] 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> list = new ArrayList<>(); for(int i=0; i()); } 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> 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); } }

결과 화면

from http://nato-blog.tistory.com/162 by ccl(A) rewrite - 2021-12-22 23:26:37