[백준] 4256-트리(C++)

문제링크: https://www.acmicpc.net/problem/4256

4256번: 트리

 

접근방식

 

1. 두 가지 순회방법을 통해서 남은 한가지 순회방법을 찾을 수 있다.

 

전위는 root노드 - root기준 왼쪽 자식노드 - root기준 오른쪽 자식노드 순으로 표시되고

중위는 root기준 왼쪽 자식노드 - root노드 - root기준 오른쪽 자식노드 순으로 표시된다.

-> 그렇다면 후위순회 함수를 구현하며 노드 값을 출력하며 결과를 도출할 수 있다. 

 

2. 전위 순회함수로 탐색을 하며 root값에 해당하는 중위순회값을 매개변수로 전달하며 진행

3. 재귀함수, 분할정복으로 구현하였다.

 

 

문제풀이 

1. 분할정복으로 구현 

2. 전위순회를 기준으로 root 노드를 출력하는 형태

 

아래는 정답 코드입니다.

#include <iostream>
using namespace std;

int t;
int n;
int pre[1000] = { 0, };
int ino[1000] = { 0, };

void solved(int pl, int pr, int il, int ir) {
	if ((pr - pl) == 0) {
		cout << pre[pl] << ' ';
		return;
	}

	for (int i = 0; i <= pr - pl; i++) {
		if (pre[pl] == ino[il + i]) {
			solved(pl + 1, pl + i, il, il + i - 1);
			solved(pl + i + 1, pr, il + i + 1, ir);
			cout << pre[pl] << ' ';
			return;
		}

	}

}

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

	cin >> t;

	while (t--) {
		cin >> n;

		for (int i = 0; i < n; i++)
			cin >> pre[i];
		for (int i = 0; i < n; i++)
			cin >> ino[i];

		solved(0, n - 1, 0, n - 1);
		cout << "\n";
	}

	cout << "\n";
	return 0;
}