트리 순회 순서 변경 문제

트리 순회 개념

 

전위 순회 : 루트 -> 왼쪽 -> 오른쪽

중위 순회 : 왼쪽 -> 오른쪽 -> 루트

후위 순회 : 왼쪽 -> 오른쪽 -> 루트

 

 

문제

 

테스트 케이스의 수 C(1<=C<=100) 주어지고 노드의 수 (1<=N<=100)

그 후 두줄에 각각 트리를 전위 순회했을 때와 중위순회 했을 떄의 노드 방문 순서가 N개의 정수로 주어진다.

 

출력 각 테스트마다 한 줄에 해당 트리의 후위 순회했을 대 노드들의 방문 순서를 출력한다.

 

 

 

#include
#include
#include
using namespace std;
#define MAX 101
vector preorder,inorder,postorder;
vector slice(const vector&v, int a, int b) {
	return vector(v.begin() + a, v.begin() + b);
}

void printPostOrder(const vector&preorder, const vector&inorder) {
	//트리에 포함된 노드의 수
	const int N = preorder.size();
	//기저 사례: 텅 빈 트리면 곧장 종료
	if (preorder.empty())return;
	//이 트리의 루트는 전위 탐색 결과로부터 곧장 알 수 있다.
	const int root = preorder[0];
	//이 트리의 왼쪽 서브트리의 크기는 중위탐색결과에서 루트의 위치를 찾아서 알 수 있다.
	const int L = find(inorder.begin(), inorder.end(), root)-inorder.begin();
	//오른쪽 서브트리의 크기는 N에서 왼쪽 서브트리와 루트를 빼면 알 수 있다.
	const int R = N - 1 - L;
	
	//왼쪽과 오른쪽 서브트리의 순회 결과를 출력
	printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
	printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
	
	//후위 순회이므로 루트를 가장 마지막에 출력한다.
	cout << root << '\n';
	
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int testCase;
	cin >> testCase;
	for (int tc = 1; tc <= testCase; tc++) {
		int n;
		cin >> n;
		for (int i = 0; i < n; i++) {
			int num;
			cin >> num;
			preorder.push_back(num);
		}
		for (int i = 0; i < n; i++) {
			int num;
			cin >> num;
			inorder.push_back(num);
		}
		printPostOrder( preorder, inorder);
	}
	return 0;
}

예제 입력

1

7

27 16 9 12 54 36 72

9 12 16 27 36 54 72

 

예제 출력

12 9 16 36 72 54 27