BOJ 4256 - 트리(Java)

https://www.acmicpc.net/problem/4256

4256번: 트리

 

풀이

전위 순회 : 현재 노드 -> 왼쪽 노드 -> 오른쪽 노드

중위 순회 : 왼쪽 노드 -> 현재 노드 -> 오른쪽 노드

* 전위 순회의 0번째 노드는 현재 노드, 중위 순회 요소에서 현재 노드를 기준으로 왼/오른쪽 노드로 나뉨

위의 2가지 순회로 트리 구조 및 후위 순회 파악 가능

 

now= 0을 루트로 [0 ~ N]의 범위에 대해 탐색

1. preOrder[now] = 현재 노드

2. preOrder[now] = inOrder[idx]의 위치를 탐색 

    - inOrder[idx]값을 포함하지 않은 왼쪽 요소들 = 왼쪽 노드에 포함

    - inOrder[idx]값을 포함하지 않은 오른쪽 요소들 = 오른쪽 노드에 포함

3. 왼쪽 노드 탐색

    - now= now +1, [begin ~ idx - 1]의 범위에 대해 1로 재귀

4. 오른쪽 노드 탐색

    - now = (now + idx - begin + 1), [idx+1 ~ end]의 범위에 대해 1로 재귀

    * (- begin)을 하는 이유 = now + idx를 할 경우 [0 ~ begin]이 중복되기 때문에

5. 현재 노드 출력

 

 

전체 코드

import java.io.*;
import java.util.*;

public class Main {

    static int T, N;
    static int[] preOrder, inOrder;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());

        for (int test = 0; test < T; test++) {
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            preOrder = new int[N];
            inOrder = new int[N];

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                preOrder[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                inOrder[i] = Integer.parseInt(st.nextToken());
            }

            findPostOrder(0, 0, N - 1);
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

    private static void findPostOrder(int rootIdx, int begin, int end) {
        if(rootIdx>=N) {
            return;
        }

        int rootValue = preOrder[rootIdx];
        
        for (int idx = begin; idx <= end; idx++) {
            if (rootValue == inOrder[idx]) {
                findPostOrder(rootIdx + 1, begin, idx);
                findPostOrder(rootIdx + idx + 1 - begin, idx + 1, end);
                sb.append(rootValue + " ");
                return;
            }
        }
    }
}