[알고스팟][C++] TRAVERSAL: 트리 순회 순서 변경

문제 링크: https://algospot.com/judge/problem/read/TRAVERSAL

(출처: 종만북)

 

pre-order, in-order로 트리를 순회한 순서가 나올 때 post-order로 트리를 순회한 결과를 출력하는 문제입니다.

pre-order로 순회했을 때 첫번째로 오는 노드가 root 노드라는 점을 이용할 수 있는데요, in-order에서 root 노드의 위치를 찾아 root 전에 방문했으면 왼쪽 서브트리, 아니면 오른쪽 서브트리를 만들고 각 서브트리에 대해 post-order 출력을 재귀적으로 수행하면 됩니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

vector<int> v_slice(const vector<int>& v, int from, int to) {
	return vector<int>(v.begin()+from, v.begin()+to);
}

void printPostOrder(const vector<int>& preorder, const vector<int>& inorder) {
	const int N = preorder.size();

	if (preorder.empty()) return;

	const int root = preorder[0];

	// 왼쪽 서브트리의 크기
	const int left_length = find(inorder.begin(), inorder.end(), root) - inorder.begin();

	printPostOrder(v_slice(preorder, 1, left_length+1), v_slice(inorder, 0, left_length));
	printPostOrder(v_slice(preorder, left_length+1, N), v_slice(inorder, left_length+1, N));

	cout << root << ' ';
}

int main()
{

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		vector<int> preorder(n), inorder(n);
		for (auto& c : preorder)
			cin >> c;
		for (auto& c : inorder)
			cin >> c;

		printPostOrder(preorder, inorder);
		cout << '\n';
	}

	return 0;
}