[C++] 백준 6597번: 트리 복구

 

https://www.acmicpc.net/problem/6597

6597번: 트리 복구

 

 > 접근

위 사진에서 preorder의 첫번째 문자열인 D를 통해, inorder에서 D가 루트 노드이며, ABC, EFG가 각각 left, right라는 것을 알 수 있다. 다음에는 두번째 문자열인 B로, ABC에서 B가 루트라는 것을 알 수 있다. 이러한 로직이 구조적으로 반복될 수 있다.

이를 기반으로 간단한 재귀 함수 하나를 짜면 다음과 같이 나온다.

void f(int start, int end) {
	if (start > end) return;

	int mid = inorder.find(preorder[preorderIndex++]);

	f(start, mid - 1);
	f(mid + 1, end);
}

이 함수를 통해, root부터 시작하는 dfs 탐색이 가능해진다. 여기에, postorder 순서로 출력문을 하나 넣으면 이 문제가 해결된다.

 

#include <bits/stdc++.h>
using namespace std;

string preorder, inorder;
int preorderIndex;

void f(int start, int end) {
	if (start > end) return;

	int mid = inorder.find(preorder[preorderIndex++]);

	// postorder
	f(start, mid - 1);
	f(mid + 1, end);
	cout << inorder[mid];
}

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

	while (true) {
		preorder.clear();
		inorder.clear();
		cin >> preorder >> inorder;
		int len = preorder.length();

		// 탈출 조건
		if (len == 0) break;

		preorderIndex = 0;
		f(0, len - 1);
		cout << "\n";
	}

	return 0;
}