[백준 4256] 트리

문제 링크 => 4256번: 트리 (acmicpc.net)

4256번: 트리

---

트리를 이용한 분할정복 문제이다.

 

이 문제는 preorder와 inorder가 주어졌을때 postorder를 구하는 문제인데 약간 까다로웠다.

 

먼저 예시를 살펴보도록 한다.

 

preorder :  3 6 5 4 8 7 1 2

inorder : 5 6 8 4 3 1 2 7

 

preorder의 맨 앞부분 3은 트리의 가장 위에 있는 노드이다.

 

그리고 inorder를 살펴보면 3을 기준으로 5 6 8 4 는 3의 왼쪽 자식이고 1 2 7 은 3의 오른쪽 자식이다.

 

이때 5 6 8 4는 preorder에서 6 5 4 8 이고 1 2 7은 preorder에서 7 1 2 이다.

 

따라서 preorder의 첫 노드와 inorder의 i번째 노드가 동일할 때 다음과 같이 재귀적으로 호출해 줘야 한다.

 

if preorder[x] == inorder[i]  // preorder의 x번째 노드와 inorder의 i번째 노드와 동일할 경우 

postorder(front, i, x+1);  //  x+1은 preorder의 맨 앞부분의 그 다음 부분을 나타냄

postorder(i+1, back, x+1+(i-front));  // 여기서 i-front를 더하는 이유는 preorder의 맨 앞에 존재하는 x번째 노드를 기준으로 오른쪽 자식들 중 preorder의 앞부분을 나타내기 위함이다.

cout << inorder[i] << " ";  // inorder의 i번째 노드를 호출하거나 preorder의 x번째 노드를 호출해준다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

vector<int> v1, v2; // Preorder, Inorder

void postOrder(int front, int back, int x) {
	for (int i = front; i < back; i++) {
		if (v1[x] == v2[i]) {
			postOrder(front, i, x + 1);
			postOrder(i + 1, back, x + 1 + i - front);
			cout << v1[x] << " ";
		}
	}
}

void test() {
	v1.clear(), v2.clear();
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v1.push_back(x);
	}
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v2.push_back(x);
	}
	postOrder(0, n, 0);
	cout << endl;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		test();
	}

	return 0;
}