백준 4256번: 트리 (Java)

접근

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

4256번: 트리

전위 순회, 중위 순회가 주어진 트리를 후위 순회 방식으로 표시하는 문제였습니다.

전위 순회의 경우 트리에서 루트 노드를 가장 먼저 표시합니다. 이 점을 이용하여 다음과 같이 재귀적으로 문제를 해결할 수 있습니다.

1. 전위 순회에서 가장 앞의 숫자를 꺼냅니다.
2. 꺼내진 숫자를 중위 순회에서 찾습니다. 해당 인덱스를 기준으로 앞쪽은 왼쪽 자식 중위 순회, 뒤쪽은 오른쪽 자식 중위 순회입니다.
3. 전위 순회의 다음 숫자를 꺼내면, 다시한번 이 숫자를 앞에서 구한 왼쪽 자식 중위 순회에서 찾습니다.

찾는 과정을 모두 거치고, 맨 처음에 꺼낸 숫자를 맨 뒤에 붙여주면 후위 순회 순서대로 배열이 완성됩니다.

코드

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

public class Main {

  static int T, n;
  static int[] preorder, inorder;
  static LinkedList<Integer> backorder;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    T = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();
    for (int t = 0; t < T; t++) {
      n = Integer.parseInt(br.readLine());
      preorder = new int[n + 1];
      inorder = new int[n + 1];
      backorder = new LinkedList<>();
      StringTokenizer 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());
      }
      makeBackorder(0, 0, n);
      for (int i = 0; i < n; i++) {
        sb.append(backorder.poll()).append(' ');
      }
      sb.append('\n');
    }
    br.close();
    System.out.print(sb.toString());
  }

  static void makeBackorder(int rootIdx, int s, int e) {
    int root = preorder[rootIdx];
    for (int i = s; i < e; i++) {
      if (inorder[i] == root) {
        makeBackorder(rootIdx + 1, s, i);
        makeBackorder(rootIdx + i + 1 - s, i + 1, e);
        backorder.add(root);
      }
    }
  }
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!