[백준]2263번 트리의 순회

2263번: 트리의 순회

Inorder, Postorder가 given되었을 때!!! preOrder를 구하기

• Inorder : left chlid → 자신 → right child
• PostOrder : Left child → Right child → 자신 =⇒ 즉, 맨 마지막에 출력되는 노드가 root

모르겠다 - 방법 1 :

20 분정도 고민만을 해 보았지만 모르겠었다. 문제 자체의 이해가 아닌 풀이 자체에 전혀 감이 잡히지 않아 이와 관련된 내용을 찾아보았다.

• 위에서 생각한 것 처럼, PostOrder traverse에서 마지막으로 출력된 숫자 → root node다.
  • PreOrder은 , sub tree의 root node들부터 방문하는 것이나 다름없기 때문에, 이 root node를 출력 해 나가는 것으로 하면 된다.
  • Inorder에서, 이 root node를 탐색한다.
    • Inorder를, root node를 중심으로, left, right subtree로 나눈다.
• 이를 반복한다.

즉 예를들어

		2
	1    3
4  5  8   
	6 7  9
ROOT를 중심으로 보면 
IN은   LEFT -> ROOT -> RIGHT
POST는 LEFT -> RIGHT -> ROOT
따라서, IN에서 ROOT를 중심으로 LEFT, RIGHT SUBTREE가 나뉘어지고
POST에서는 ROOT앞에, RIGHT TREE가 존재한다. 

의 IN   : 4 | [1] | 6 [ 5 ] 7 | [2] | 8 9 [3] 
의 POST : 4 | 6 7 [5] [1] | 9 8 [3] |[2]

9
4 1 6 5 7 2 8 9 3
4 6 7 5 1 9 8 3 2
// 2 1 4 5 6 7 3 8 9

7
1 2 3 4 5 6 7
1 3 2 5 7 6 4
		4
	2   6
1  3 5  7

9
7 9 4 2 5 1 3 6 8
9 7 4 5 2 8 6 3 1
//1 2 4 7 9 5 3 6 8

• 일종의 분할정복인가? 라고 생각할 수도 있다 . 문제는 위의 방식대로라면, in에서 매 번 root를 찾아야 하기 때문에, 결국은 O(n^2)의 시간복잡도를 갖게 된다. ( search를 전체탐색을 통해서 구하지 않으면 되긴 하겠다)

구현

len = in.length;

• left =0, right = len;
  • root = post[right]
  • search root from the in array → x
  • left ~ x-1 , x+1~right

시간복잡도 : O(n^2)

• 이 문제의 경우 N은 최대 10만이하이기 때문에, 엄청난 시간이 걸릴 것으로 예상된다.
• 이 방법을 사용해도 통과할 수 있도록 이 문제는 제한시간이 무려 5초나 된다.

개선해보기

• in에서 root를 탐색하는 부분을 O(1)의 효율로 바꾸면 된다.
• map을 사용해서, 입력을 받을 때 부터, Inorder의 수를, index와 매핑시켜 저장한다.
• 또는 현재 n이 10만개밖에 되지 않기 때문에, 그냥 배열에다가 index를 저장해도 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int[] in = new int[100001];
    public static int[] post = new int[100001];

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static  int n;
    public static Map<Integer,Integer> map = new HashMap<>(); // 특정수와 index를 매핑
    public static void setting()throws IOException{
        n = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        for (int i=0; i < n; i++) {
            in[i] = Integer.parseInt(st.nextToken());
            map.put(in[i],i);
        }

        st = new StringTokenizer(br.readLine());
        for (int i=0; i < n; i++) post[i] = Integer.parseInt(st.nextToken());

    }
    // In 에서 root 위치 찾기
    public static int searchRoot(int left, int right, int root){
        for(int i=left;i<=right;i++){
            if(in[i]==root) return i;
        }
        return -1;
    }
    // in 에서의 범위 post에서의 범위
    public static void solve(int left,int right,int pleft,int pright){
        //System.out.println("left :"+left+", right: "+right);
        if(left<0 || right>=n || left>right) 
            return;
        int root = post[pright];
        //int rootidx = searchRoot(left,right,root);
        int rootidx = map.get(root);
        int len = rootidx - left;
        System.out.print(in[rootidx]+" ");
        solve(left,rootidx-1, pleft,pleft+len-1);
        solve(rootidx+1,right, pleft+len,pright-1);
    }
    public static void main(String[] args)throws IOException {
        setting();
        solve(0,n-1,0,n-1);

    }

}