[TRAVERSAL] 트리 순회 순서 변경

• 분류: 그래프
• 난이도: 하
• 입력: 테스트 케이스 C(<=100), 노드의 수 N(<=100), 노드 번호 1000 이상의 자연수, 전위순회 중위순회의 결과
• 출력: 전위순회, 중위순회 결과를 바탕으로 한 후위순회 결과

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

void printPostorder(const int, int&, int, int);

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

	for (int i = 1; i <= C; i++){
		int N;
		cin >> N;
		preorder = vector<int>(N, 0);	//초기화
		inorder = vector<int>(N, 0);

		for (int j = 0; j < N; j++)
			cin >> preorder[j];
		for (int j = 0; j < N; j++)
			cin >> inorder[j];

		int index = 0;
		printPostorder(N, index, 0, N - 1);
		cout << endl;
	}
	return 0;
}

void printPostorder(const int n, int& root_index, int left, int right){
	if (left > right){
		--root_index;
		return;
	}

	if (root_index >= n) return;

	int index = left;
	for (; index <= right; index++)
		if (preorder[root_index] == inorder[index]) 
			break;

	printPostorder(n, ++root_index, left, index - 1);	//왼쪽 출력
	printPostorder(n, ++root_index, index + 1, right);	//오른쪽 출력

	cout << inorder[index] << " ";	//루트 출력
}

• 소스설명: 

1. printPostorder(const int, int&, int, int) : 전위순회가 루트→왼쪽 노드→오른쪽 노드 순으로 방문하고 중위순회가 왼쪽 노드

→루트→오른쪽 노드 순으로 방문하는 것을 이용하였다. 루트를 이용하여 중위순회를 왼쪽 서브트리와 오른쪽 서브트리로 나눠 재귀함수처럼 돌아간다.

• 참고문제: https://algospot.com/judge/problem/read/TRAVERSAL