BOJ_트리의 순회 _2263 (Java)

문제 링크

성능 요약

메모리: 72892 KB, 시간: 508 ms

분류

분할 정복, 재귀, 트리

제출 일자

2025년 1월 2일 00:55:10

문제 설명

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력

첫째 줄에 프리오더를 출력한다.

느낀점

• 인오더, 포스트오더 출력의 규칙을 고민하고 활용해볼 수 있었다.
• 코드를 좀더 리팩토링할 수 있을 것 같긴하다.
• 테케가 하나뿐이어서 설계하면서 사용한 테스트케이스를 직접 만들어 사용해봤다.

설계 : 30분

• 포스트오더 출력을 거꾸로 순회하며, 인오더 출력과 비교했을때 양쪽에 노드가 있는지 판단하면서 트리를 생성한 후 인오더를 출력한다.
• 포스트오더를 반대로 순회하면 먼저 방문할수록 가능한 우선순위는 부모 → 오른쪽자식 → 왼쪽 자식 순이다.
• 방문한 번호에 대해 인오더 출력 결과에서 오른쪽에 숫자가 있고, 아직 방문하지 않았다면 오른쪽 자식이 있다.
• 방문한 번호에 대해 인오더 출력 결과에서 왼쪽에 숫자가 있고, 아직 방문하지 않았다면 왼쪽 자식이 있다.
• 오른쪽 자식이 있다면 포스트오더 역순에서 다음으로 방문하는 숫자가 오른쪽 자식이다.
• 오른쪽 자식이 없거나 이미 채웠다면, 포스트오더 역순에서 다음으로 방문하는 숫자가 왼쪽 자식이다.

코드(Java)

• 구현 시간: 40분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 트리의 순회_문2263
 * Date: 2025.01.01
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static int[] inOrder;
    static int[] inOrderPrint;
    static int[] postOrderPrint;
    static int n;
    static boolean[] visited;
    static int idx;
    static Node[] tree;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

        n = Integer.parseInt(br.readLine());
        inOrder = new int[n+1];     // 각 숫자의 인오더 출력 순서
        inOrderPrint = new int[n+1];      // 인오더 출력 내용
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            int num = Integer.parseInt(st.nextToken());
            inOrderPrint[i] = num;
            inOrder[num] = i;
        }
        postOrderPrint = new int[n+1];     // 포스트오더 출력 내용
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 1; i <= n; i++) {
            postOrderPrint[i] = Integer.parseInt(st.nextToken());
        }

        visited = new boolean[n+1];     // 해당 숫자의 노드 방문여부
        tree = new Node[n+1];
        for (int i = 0; i <= n; i++) tree[i] = new Node(i);
        idx = n;
        Node root = tree[postOrderPrint[idx--]];
        makeTree(root);

        printInOrder(root);
		bw.flush();
		bw.close();
		br.close();
	}

    private static void printInOrder(Node root) throws IOException {
        bw.write(String.valueOf(root.num) + " ");
        if (root.left > 0) printInOrder(tree[root.left]);
        if (root.right > 0) printInOrder(tree[root.right]);
    }

    private static void makeTree(Node curr) {
        int order = inOrder[curr.num];

        visited[curr.num] = true;

        if (order+1 <= n && !visited[inOrderPrint[order+1]]) {
            curr.right = postOrderPrint[idx--];
            makeTree(tree[curr.right]);
        }
        if (order-1 > 0 && !visited[inOrderPrint[order-1]]) {
            curr.left = postOrderPrint[idx--];
            makeTree(tree[curr.left]);
        }
    }
}

class Node {
    int num;
    int left;
    int right;

    Node(int num) {
        this.num = num;
        this.left = -1;
        this.right = -1;
    }
}