[BOJ_4256] 트리

설명

---

처음에는 이분탐색 느낌으로 풀 수 있을까 싶었는데 그런 느낌 보다는 root 값이 위치한 곳을 찾아야 한다. 왼쪽의 경우에는 어찌 어찌 찾아 가겠으나 오른쪽에 있는 문제들은 결국 같은 로직으로 찾을 수 없으니 직접 preOrder의 첫번째 부분이랑 inOrder의 preOrder의 첫번째 부분과 같은 부분을 찾아야 한다.

 

참고로 전위 순회는 root -> left -> right이니 처음 나오는 곳들이 모두 해당 노드의 root가 되는 것이다. 그래서 루트 위치찍고 inOrder의 경우에는 root 위치로 부터 다음 left,right를 주기 위한 조건으로 사용하게 된다.

 

위 말이 이해가 되지 않는다면 내가 참고한 블로그 링크를 참조하면 되겠다. 

[BOJ] 백준 4256번 트리 (Java)

 

위 블로그에서 저 트리 구조가 어떻게 내려오는지를 잘 보면 구현하는데 어려움이 없을 것으로 판단 된다. 

 

이번 문제는 다른 느낌으로 정답에 근접했으나 다른 PS 블로그를 참조하여 깔끔하게 풀 수 있었던 문제다.

 

코드

---

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

public class Main {
    static int [] inOrder,preOrder;
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");
        int T = Integer.parseInt(tk.nextToken());

        while (T-- > 0){
            tk = new StringTokenizer(in.readLine()," ");
            int N = Integer.parseInt(tk.nextToken());

            preOrder = new int[N];
            inOrder = new int [N];

            tk = new StringTokenizer(in.readLine()," ");
            for (int i = 0; i < N; i++){
                preOrder[i] = Integer.parseInt(tk.nextToken());
            }

            tk = new StringTokenizer(in.readLine()," ");
            for (int i = 0; i < N; i++){
                inOrder[i] = Integer.parseInt(tk.nextToken());
            }
            getRoot(0,N,0);
            System.out.println();
        }
    }
    private static void getRoot(int root, int right, int left){
        if(right <= left || right < 0){
            return;
        }
        int rootIdx = 0;
        for (int i = 0; i < inOrder.length; i++) {
            if (preOrder[root] == inOrder[i]) {
                rootIdx = i;
                getRoot(root + 1, rootIdx, left);
                getRoot(root + rootIdx + 1 - left, right, rootIdx + 1);
                System.out.print(inOrder[rootIdx] + " ");
            }
        }
    }
}

 

4256번: 트리