백준 2263번 : 트리의 순회 [자바]

 

 

🧫 문제 분석

✔️ 출처

트리의 순회 골드 1

 

📖 문제

이진 트리 (완전 이진 트리 X) 이기에 한쪽으로 기울어긴 트리가 가능하다. 

때문에 직접 배열로 이진트리를 만들 생각을 하면 안된다. 

 

순회 특징

후위 순회는 마지막이 항상 중앙노드다. 

중앙 순회는 중앙노드 기준으로 왼쪽, 오른쪽 서브트리를 갖는다.

 

중앙노드, 서브트리, 왼쪽 끝 오른쪽 끝 노드를 알 수 있는데 어떻게 해야 전위순회를 할 수 있을까

 

분할 정복을 이용하면 쉽게 알 수 있다.

후위 순회의 마지막 노드는 항상 중앙노드이므로 

중앙 노드를 얻고 이 노드의 중앙 순회에서 위치를 얻은다음 

중앙 순회에서 중앙 노드를 기준으로 왼쪽을 서브트리, 오른쪽을 서브트리로 나눠서 분할한다.

 

나눠지면 또 그 서브트리에서의 후위 순회의 마지막 노드는 그 서브트리의 중앙노드이다. 

이런식으로 분할하면서 정복하면 된다. 

 

 

핵심은 어떻게 서브트리 범위를 나눌 것인가인데

start ~ 중앙 노드 idx -1, 중앙 노드 +1 ~ end 로 단순히 나누면안되고

두 순회가 서로 다른 순서를 가지므로 각각에 대하여 범위를 나눈다.

 

중앙 순회에서 중앙노드까지의 거리 즉, 왼쪽 서브트리의 개수를 구한다.

이는 후위순회에서 왼쪽 서브트리의 개수이기도 하다. ( -1 을 해줘야 중앙노드를 뺀 진짜 왼쪽 서브트리가 됨)

 

이를 이용해서

// 왼쪽 탐색 
inorder시작 ~ inorder 중앙 노드 위치 - 1,
postorder시작 ~ postorder시작 + 왼쪽 서브트리 개수 - 1



// 오른쪽 탐색
inorder 중앙 노드 위치 + 1, inorder 끝,
postorder시작 + 왼쪽 서브트리 개수 ~ postorder끝 - 1
 (여기서 끝 - 1을 하는 이유는 후위 순회에서 마지막이 중앙이고 해당 값은 이미 사용했으므로 그 다음 중앙 값을 가리키기 위함이다.)

 

 

 

 

 

ps. 이 문제를 푸는데 시간이 2시간 좀 넘었는데 

이것저것 방법을 생각해 보다가  재귀로 풀면 되지 않을까 싶었는데 어떻게 중앙을 얻고 나눌지를

생각하느라 1시간 쓰고, 중앙 순회를 이용해서 중앙 노드를 찾고 왼쪽 오른쪽 서브트리를 나누는것 까지 알게되었다.

 

 

 

 

 

---

🔅 문제 풀이

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

public class Main {
    static int[] indexing; // inOrder의 중앙 위치를 빠르게 찾기 위한 인덱싱
    static int[] inorder;
    static int[] postorder;
    static int n;

    static StringBuilder sb = new StringBuilder();

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

        inorder = new int[n + 1];
        postorder = new int[n + 1];
        indexing = new int[n + 1];
        StringTokenizer stInOrder = new StringTokenizer(br.readLine());
        StringTokenizer stPostOrder = new StringTokenizer(br.readLine());

        for (int i = 1; i <= n; i++) {
            inorder[i] = Integer.parseInt(stInOrder.nextToken());
            postorder[i] = Integer.parseInt(stPostOrder.nextToken());
            indexing[inorder[i]] = i;
        }

        // 이진트리의 최상 중앙, 왼쪽, 오른쪽 구하기
        createBinaryTree(1, n, 1, n);

        System.out.println(sb.toString());
    }

    private static void createBinaryTree(int inStart, int inEnd, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd) return;
        // 중앙 즉, 현재 최상위 부모
        int mid = postorder[postEnd];
        sb.append(mid).append(" ");

        // inorder에서 중앙 값 기준 왼쪽 서브트리의 개수를 구한다.
        // postOrder에서도 왼쪽 서브트리의 개수가 있을 것이고 이진트리이기에 inorder의 왼쪽 서브트리 개수와 같다.
        int postSize = indexing[mid] - inStart;

        // 중앙 기준
        createBinaryTree(inStart, indexing[mid] - 1, postStart, postStart + postSize - 1); // 왼쪽
        createBinaryTree(indexing[mid] + 1, inEnd, postStart + postSize, postEnd - 1); // 오른쪽

    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1.  트리의 속성에 대해 잘 이해했다면 쉽게 풀었을텐데 아쉽다. 접근 자체는 잘 했는데 후의 순회 범위 나누는 것을 잘 못했고 구현이 어려웠다.