<백준> 2263

트리의 순회

문제
n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

입력
첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.

출력
첫째 줄에 프리오더를 출력한다.

전위 순회(preorder) -> 루트 - 왼쪽 - 오른쪽
중위 순회(inorder) -> 왼쪽 - 루트 - 오른쪽
후위 순회(postorder) -> 왼쪽 - 오른쪽 - 루트

중위와 후위가 주어졌을 때 전위순회를 구하는 문제다. 루트는 후위 순회의 맨마지막 수이기에 구하기 쉽다. 그렇게 재귀로 root를 찾아가면 된다.

int n;
vector<int> inorder, postorder;
unordered_map<int, int> m;

void makePreorder(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd)
{
	if (inorderStart > inorderEnd || postorderStart > postorderEnd)
		return;

	int root = postorder[postorderEnd];
	cout << root << " ";

	int rootIdx = m[root];
	int leftSize = rootIdx - inorderStart;

	makePreorder(inorderStart, rootIdx - 1, postorderStart, postorderStart + leftSize - 1);
	makePreorder(rootIdx + 1, inorderEnd, postorderStart + leftSize, postorderEnd - 1);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int value;
		cin >> value;
		inorder.push_back(value);
		m[inorder[i]] = i;
	}

	for (int i = 0; i < n; i++)
	{
		int value;
		cin >> value;
		postorder.push_back(value);
	}
	makePreorder(0, n - 1, 0, n - 1);
	return 0;
}