[백준] 4256 - 트리

[백준] 4256 - 트리

[문제링크]

1. 현재 노드 x를 기준으로, 전위 순회는 x-[왼쪽]-[오른쪽] 의 순서로, 중위 순회는 [왼쪽]-x-[오른쪽]의 순서로 만들어진다

2. 즉, 전위 순회 결과의 첫 노드를 기준으로, 중위 순회의 왼쪽과 오른쪽을 분리할 수 있다.

3. 또한 왼쪽과 오른쪽 subtree에 대해서도 동일한 작업으로 분리할 수 있다.

최종적으로 tree의 크기가 1이 되면, leaf 노드가 된다

4. tree를 입력받아, root 노드를 만들어 반환하는 함수를 만들 수 있다.

두 자식 노드는 동일 함수에 left/right subtree에 대해 재귀 돌려 구할 수 있다.

5. 이때 재귀 순서를 왼쪽->오른쪽으로 진행하면, 전위 순회와 진행 순서가 일치하게 된다

즉, 매 재귀 단계마다 전위순회의 다음번 노드가 곧 root노드가 된다 (전역변수로 관리)

중위 순회의 left/right만 관리하면 된다

6. 복원한 원형 tree로부터 후위 순회 결과를 얻어낸다

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static class node{ int num; node left; node right; node(int num){ this.num=num; } } static int cnt; static int[] pre; static int[] in; static StringBuilder sb; public static void main(String[] args)throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int tc = pint(br.readLine()); for (int test = 1; test <= tc; test++) { int n = pint(br.readLine()); pre = new int[n]; in = new int[n]; cnt=0; StringTokenizer st = new StringTokenizer(br.readLine(), " "); StringTokenizer st2 = new StringTokenizer(br.readLine(), " "); for (int j = 0; j < n; j++) { pre[j]=pint(st.nextToken()); in[j]=pint(st2.nextToken()); } node head = restore(0, n); //restore original tree sb = new StringBuilder(); postorder(head); System.out.println(sb); } } static node restore(int s, int e) { if(s==e)return null; //leaf node int cur = pre[cnt++]; //head of current subtree node n = new node(cur); //node for (int i = s; i < e; i++) { if(cur==in[i]) { n.left=restore(s, i); //left child n.right=restore(i+1, e); //right child } } return n; } static void postorder (node n) { if(n.left!=null)postorder(n.left); if(n.right!=null)postorder(n.right); sb.append(n.num).append(" "); } static int pint(String s) { return Integer.parseInt(s); } }

결과 화면

from http://nato-blog.tistory.com/130 by ccl(S) rewrite - 2021-09-25 06:00:48