[백준] 2263 트리의 순회 - JAVA

문제

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

풀이

입력으로 인오더와 포스트오더가 주어진다.

인오더는 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문하고 (LVR)
포스트오더는 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문한다.(LRV)

다음과 같은 이진 트리가 있다고 가정해 보자.

            1

        /       \

     2            3

 /     \       /     \

4       5     6       7

|       |     |       |

8       9     10     11

해당 트리에서 인오더를 한 결과는 8 4 2 9 5 1 10 6 3 11 7과 같고
포스트오더를 한 결과는 8 4 9 5 2 10 6 11 7 3 1와 같다.

포스트오더는 루트노드를 제일 마지막에 방문하므로 포스트오더의 제일 마지막으로 방문한 노드는 이진 트리의 최상위 루트 노드가 된다.
즉 8 4 9 5 2 10 6 11 7 3 1에서 제일 마지막에 있는 1이 최상위 루트 노드가 된다.

그렇다면 인오더로는 어떤것을 알 수 있을까? 인오더는 위에 언급했다 싶이 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문한다. 그럼 다시 인오더를 봐보자
8 4 2 9 5 1 10 6 3 11 7 최상위 루트 노드인 1을 기점으로 왼쪽과 오른쪽으로 나누면 다음과 같다
8 4 2 9 5 | 1 | 10 6 3 11 7 이것을 통해 알 수 있는 사실은 루트노드를 기점으로 왼쪽에 있는 값들은 왼쪽 자식노드, 오른쪽에 있는 값들은 오른쪽 자식 도느에 해당함을 알 수 있다.

우리가 구할려고 하는 프리오더는 루트노드를 방문한 후 왼쪽 서브트리, 오른쪽 서브트리를 방문하므로
포스트오더로 알아낸 루트노드를 인오더에서 몇번째 인덱스에 루트노드가 존재하는지 알아낸 뒤 해당 루트노드를 기점으로 왼쪽과 오른쪽으로 나누면 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리가 된다.

위의 방식대로 예를들자면
인오더: 8 4 2 9 5 1 10 6 3 11 7
포스트오더: 8 4 9 5 2 10 6 11 7 3 1

포스트오더의 제일 마지막 값은 루트 노드이고 우리가 구할려고 하는 프리오더는 루트 노드를 제일 먼저 방문 하므로 해당 값을 출력해준다.
1 ->
그런다음 인오더에서 1에 해당하는 인덱스 값을 알아낸 뒤 왼쪽서브트리와 오른쪽서브트리를 나누고 나눈 트리에서 또다시 루트노드를 찾아 낸다.
8 4 2 9 5 | 10 6 3 11 7
8 4 9 5 루트 노드: 2 | 10 6 11 7 루트 노드: 3
...
이런식으로 계속 분할하고 반복하는 과정은 재귀를 통해서 구현해준다.
분할을 계속하고 만약 분할했을때 노드가 하나밖에 없을때까지 반복한다.

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

public class Main {
  static StringBuffer sb = new StringBuffer();
  static int[] inorder;
  static int[] inorderIndex;
  static int[] postorder;
  static int n;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    inorder = new int[n];
    postorder = new int[n];
    inorderIndex = new int[n+1];
    st = new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++) {
      inorder[i] = Integer.parseInt(st.nextToken());
    }
    st = new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++) {
      postorder[i] = Integer.parseInt(st.nextToken());
    }
    for(int i=0; i<n; i++) {
      inorderIndex[inorder[i]] = i;
    }
    getPreOrder(0, n-1, 0, n-1);
    System.out.println(sb);
  }
  public static void getPreOrder(int in_start,int in_end,int p_start,int p_end) {
    if(in_start > in_end || p_start > p_end) {
      return;
    }

    int rootNode = postorder[p_end];
    sb.append(rootNode + " ");

    int rootIndex = inorderIndex[rootNode];
    int leftNodeLength = rootIndex - in_start;

    getPreOrder(in_start,rootIndex-1,p_start,p_start+leftNodeLength-1);

    getPreOrder(rootIndex+1, in_end, p_start+leftNodeLength, p_end-1);
  }
}