[Algorithm] 20 트리 - 3

21.3 문제: 트리 순회 순서 변경

문제

다음이 조건이 주어진다.

• 어떤 이진 트리를 전위 순회했을 때 노드들의 방문순서
• 중위 순회했을 때 노드들의 방문 순서

이 트리를 후위순회했을 때 각 노드들을 어떤 순서대로 방문하게 될지 계산하는 프로그램을 작성하라.

예제 입력

• 트리에 포함된 노드의 수 N(1≤ N ≤ 100)
• 각각 트리를 전위 순회했을 때와 중위순회 했을 때의 노드 방문 순서(N개의 정수)
• 각 노드는 1000 이하의 자연수 번호로 매겨짐

• 한 트리에서 두 노드의 번호가 같은 경우는 없음

• N = 7
• 전위: 27 16 9 12 54 36 72
• 중위: 9 12 16 27 36 54 72

예제 출력

• 후위: 12 9 16 36 72 54 27

1. 전위순회배열 preorder[0]이 루트의 번호를 찾는다. → 27
2. 중위순회배열 inorder[] 에서 root를 찾는다. → inorder[3]
   1. 중위 순회 결과에서 루트보다 먼저 방문된 노드는 왼쪽 서브트리에 존재함 → 9 12 16
   2. 늦게 방문된 노드들은 오른쪽 서브트리에 있음 → 36 54 72

구현 코드

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();
	// 기저사례: 텅빈 트리면 곧장 종료
	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 << ' ';
}

| preorder | inorder | root | L = find(..) - inorder.begin() | R | slice(preorder, 1, L+1) | slice(inorder, 0, L) | slice(preorder, L+1, N) | slice[inorder, L+1, N) | 출력 | | — | — | — | — | — | — | — | — | — | — | | 27 16 9 12 54 36 72 | 9 12 16 27 36 54 72 | 27 | 3 - 0 = 3 | 7 - 1 - 3 = 3 | [16,9,12] | [9,12,16] | [54, 36, 72] | [36, 54, 72] | | | 27 16 9 12 54 36 72 | 9 12 16 27 36 54 72 | 16 | 2 - 0 = 2 | 3 - 1 - 2 = 0 | [9,12] | [9,12] | [] | [] | —16 | | 27 16 9 12 54 36 72 | 9 12 16 27 36 54 72 | 9 | 0 - 0 = 0 | 2 - 1 - 0 = 1 | [] | [] | [12] | [12] | -9 | | 27 16 9 12 54 36 72 | 27 16 9 12 54 36 72 | 12 | 0 - 0 = 0 | 1 - 1 - 0 = 0 | [] | [] | [] | [] | 12 |