Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

28. 트리

대표적인 그래프 종류 중 하나인 트리를 다뤄 봅시다.

Java / Python

5. 트리의 순회

2263번

중위 순회와 후위 순회가 주어졌을 때 전위 순회를 구하는 문제

이번 문제는 이진 트리의 중위 순회(inorder traversal)와 후위 순회(postorder traversal)가 주어질 때, 전위 순회(preorder traversal)한 결과를 출력하는 프로그램을 작성하는 문제이다.

전위 순회 : root -> l -> r
중위 순회 : l -> root -> r
후위 순회 : l -> r -> root
후위순회를 통해서는 트리의 루트를 알 수 있고, 중위순회를 통해서는 왼쪽 자식 트리와 오른쪽 자식 트리를 알 수 있다.

• Java

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

public class Main {

	public static int N;

	static int[] in_order;
	static int[] in_order_idx; // 중위 순회 루트들의 인덱스 정보
	static int[] post_order;

	static StringBuilder sb;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		sb = new StringBuilder();

		in_order = new int[N+1];
		in_order_idx = new int[N+1];
		post_order = new int[N+1];

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

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

		for (int i = 0; i < N; i++)
			in_order_idx[in_order[i]] = i;

		getPreOrder(0, N - 1, 0, N - 1);
		bw.write(sb.toString());
        
		bw.flush();
		br.close();
		bw.close();
	}

	public static void getPreOrder(int in_start, int in_end, int p_start, int p_end) throws Exception {
		if (in_start > in_end || p_start > p_end)
			return;

		// 루트 구하기. 후위 순회의 마지막 인덱스 p_end = 루트의 인덱스
		int root = post_order[p_end];
		sb.append(root + " ");

		// 중위 순회에서 루트의 인덱스 구하
		int rootIdx = in_order_idx[root];
		// 중위 순회에서 루트 기준 왼쪽에 노드 개수 계산
		int left = rootIdx - in_start;

		// 좌측 자식 노드
		getPreOrder(in_start, rootIdx - 1, p_start, p_start + left - 1);

		// 우측 자식 노드
		getPreOrder(rootIdx + 1, in_end, p_start + left, p_end - 1);
	}
}

• Python

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))

pos = [0]*(N+1)
for i in range(N):
    pos[in_order[i]] = i # 전위 순회

def solve(in_start, in_end, p_start, p_end):
    if(in_start > in_end) or (p_start > p_end):
        return

    root = post_order[p_end] # 후위순회에서 부모노드 찾기
    print(root, end=" ")
    left = pos[root] - in_start # 왼쪽인자 갯수
    right = in_end - pos[root] # 오른쪽인자 갯수

    solve(in_start, in_start+left-1, p_start, p_start+left-1) # 왼쪽 노드
    solve(in_end-right+1, in_end, p_end-right, p_end-1) # 오른쪽 노드


solve(0, N-1, 0, N-1)