[BOJ 2263] 트리의 순회 C++/Kotlin

 

2263번: 트리의 순회

 

동꿀오소리님 풀이 참고

[백준] 2263번 트리의 순회 - C++ - DGOS | 동꿀오소리

 

 

문제풀이

 

이진 트리의 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더(전위순회)를 구하는 문제이다.

위 트리의 인오더, 포스트오더, 프리오더를 살펴보자.

 

중위 순회 : 5 6 8 4 3 1 2 7

후위 순회 : 5 8 4 6 2 1 7 3

전위 순회 : 3 6 5 4 8 7 1 2

 

굵게 표시해놓은 것이 루트 노드이다.

후위 순회는 [왼쪽 자식 - 오른쪽 자식 - 루트]순으로 순회하기 때문에 루트가 항상 마지막이다.

따라서 중위 순회 값의 인덱스를 따로 저장해두면 중위 순회에서의 루트 노드의 인덱스를 쉽게 찾을 수 있다.

 

찾아낸 루트 값을 출력해주고 더 이상 분해할 수 없을 때까지 트리의 왼쪽과 오른쪽을 탐색해주면 전위 순회를 구할 수 있다.

 

 

코드

 

C++ 코드

 

	#include <iostream>
	#define MAX 100001
	using namespace std;
	int in[MAX]; // inorder
	int post[MAX]; // postorder
	int idx[MAX]; // inorder에서 index 정보 저장
	// inorder 시작번호, inorder 끝번호, postorder 시작번호, postoder 끝번호
	void preorder(int in_left, int in_right, int po_left, int po_right)
	{
	// 더 이상 분해할 수 없는 경우 종료
	if (in_left > in_right || po_left > po_right) return;
	// postoder의 마지막 값이 root
	int rootIdx = idx[post[po_right]];
	cout << in[rootIdx] << ' ';
	// 왼쪽 서브트리 노드 개수
	int left = rootIdx - in_left;
	// 왼쪽
	preorder(in_left, rootIdx - 1, po_left, po_left + left - 1);
	// 오른쪽
	preorder(rootIdx + 1, in_right, po_left + left, po_right - 1);
	}
	int main()
	{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> in[i];
	for (int i = 0; i < n; i++) cin >> post[i];
	for (int i = 0; i < n; i++) idx[in[i]] = i;
	//preorder(0, n, n - 1);
	preorder(0, n - 1, 0, n - 1);
	return 0;
	}

view raw [BOJ 2263] 트리의 순회.cpp hosted with ❤ by GitHub

 

Kotlin 코드

 

	private var n = 0
	private lateinit var inorder : List<Int>
	private lateinit var postorder : List<Int>
	private val idx = mutableMapOf<Int, Int>()
	fun main() = with(System.`in`.bufferedReader()) {
	n = readLine().toInt()
	inorder = readLine().split(" ").map { it.toInt() }
	postorder = readLine().split(" ").map { it.toInt() }
	inorder.forEachIndexed { index, i -> idx[i] = index }
	preorder(0, n - 1, 0, n - 1)
	}
	private fun preorder(inLeft : Int, inRight : Int, postLeft : Int, postRight : Int) {
	// 범위를 벗어난 경우
	if (inLeft > inRight || postLeft > postRight) return;
	val rootIdx = idx[postorder[postRight]]!! // inorder에서 root의 위치
	val left = rootIdx - inLeft // 왼쪽 서브트리 노드 개수
	print("${postorder[postRight]} ")
	// 왼쪽
	preorder(inLeft, rootIdx - 1, postLeft, postLeft + left - 1)
	// 오른쪽
	preorder(rootIdx + 1, inRight, postLeft + left, postRight - 1)
	}

view raw [BOJ 2263] 트리의 순회.kt hosted with ❤ by GitHub