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

 이 문제는 전위 순회 결과와 중위 순회 결과를 입력으로 받아 후위 순회 결과를 리턴하는 문제이다. 

전위 순회의 경우 루왼오, 중위 순회의 경우 왼루오, 후위 순회의 경우 왼오루 순서로 노드를 방문하게 된다. 즉, 전위 순회에서는 무조건 루트부터 방문하므로 맨 앞이 루트가 된다. 전위 순회 결과로 루트를 알아낸 다음, 중위 순회 결과에서 이 루트로 왼쪽 서브트리와 오른쪽 서브트리를 알아낸다. 그 다음 후위 순회와 같이 호출해주면 쉽게 풀 수 있다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> preorder;
vector<int> inorder;
int rootIndex;

void postorder(vector<int> tree) {
	if (tree.empty()) {
		return;
	}

	int root = preorder[rootIndex];
	rootIndex++;

	vector<int> left;
	vector<int> right;

	bool flag = false;
	for (int i = 0; i < tree.size(); i++) {
		if (tree[i] == root) {
			flag = true;
			continue;
		}

		if (!flag) {
			left.push_back(tree[i]);
			continue;
		}
		right.push_back(tree[i]);
	}

	postorder(left);
	postorder(right);
	cout << root << " ";
}

int main() {
	int C;
	cin >> C;

	for (int test = 0; test < C; test++) {
		int N;

		cin >> N;

		preorder.clear();
		inorder.clear();
		rootIndex = 0;

		for (int i = 0; i < N; i++) {
			int temp;
			cin >> temp;
			preorder.push_back(temp);
		}
		for (int i = 0; i < N; i++) {
			int temp;
			cin >> temp;
			inorder.push_back(temp);
		}

		postorder(inorder);
		cout << '\n';
	}

	return 0;
}