[C++] 백준 4256 : 트리

 

 

 

문제

 

입력

 

출력

---

 

 

문제 해결

 

pl, pr : 전위 순회의 첫 번째와 마지막

il, ir : 중위 순회의 첫 번째와 마지막

 

전위 순회에서 첫 번째는 무조건 현재 트리의 루트.

중위 순회에서 현재 트리 루트의 위치를 찾으면 그 왼쪽 pl까지의 개수는 왼쪽 자식트리 노드의 개수

같은 이유로 루트의 오른쪽 pr까지의 개수는 오른쪽 자식트리 노드의 개수

 

 

 

코드

#include <iostream>

using namespace std;

int pre[1001], in[1001];

// 전위 순회의 루트는 무조건 첫 번째
// 중위 순회에서 루트의 왼쪽 pl까지의 개수 = 왼쪽 자식트리 노드 개수
// 중위 순회에서 루트의 오른쪽 pr까지의 개수 = 오른쪽 자식 트리 노드 개수

void solution(int pl, int pr, int il, int ir) {

	if (pl == pr) {
		cout << pre[pl] << ' ';
		return;
	}

	for (int i = 0; i <= pr - pl; i++) {
		if (pre[pl] == in[il + i]) {
			solution(pl + 1, pl + i, il, il + i - 1);		// 왼쪽 트리
			solution(pl + i + 1, pr, il + i + 1, ir);		// 오른쪽 트리
			cout << pre[pl] << ' ';							// 루트 출력
		}
	}

}

int main() {
	int t, n;
	cin >> t;

	while (t--) {
		cin >> n;
		for (int i = 0; i < n; i++)
			cin >> pre[i];
		for (int i = 0; i < n; i++)
			cin >> in[i];

		solution(0, n - 1, 0, n - 1);
		cout << endl;
	}
}