알고스팟 - 트리 순회 순서 변경

문제 : 트리 순회 순서 변경 (난이도 : 下)

 

https://algospot.com/judge/problem/read/TRAVERSAL

 

 분석

전위 순회 데이터를 통해 root 값을 확정적으로 알 수 있다. (preorder[0])

중위 순회 데이터를 통해 왼쪽 트리와 오른쪽 트리의 개수 파악이 가능하다.

이를 적절히 조합하면 후위 순회 데이터를 추출할 수 있다.

 

 구현

※ std::find() 함수의 활용과 printPostOrder() 호출 순서를 눈여겨보자.

vector<int> slice(const vector<int>& v, int a, int b)
{
	return vector<int>(v.begin() + a, v.begin() + b);
}

void printPostOrder(const vector<int>& preorder, const vector<int>& inorder)
{
	const int N = preorder.size();
	// base case
	if (preorder.empty()) return;

	const int root = preorder[0];
	
	const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
	const int R = N - L - 1;

	// 왼 -> 오 -> 루트
	printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
	printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));

	cout << root << ' ';
}

void inputData(vector<int>& a)
{
	for (int i = 0; i < a.size(); i++)
	{
		cin >> a[i];
	}
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		int n;
		cin >> n;
		vector<int> preorder(n), inorder(n);
		inputData(preorder);
		inputData(inorder);
		
		printPostOrder(preorder, inorder);
	}
	return 0;
}