백준 4256번 풀이

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

트리 문제다. 그 중 2진 트리 순회하는 문제였는데 많이 헷갈렸다.

트리를 전위 순회한 결과와 중위 순회한 결과가 주어지는데 전위 순회한 결과에서 제일 처음으로 나오는 숫자가 전체 트리의 루트이고, 그 다음 결과는 좌측 서브트리의 루트이다.

이런 식으로 진행이 된다.

따라서 전위 순회한 결과에서 트리의 루트를 순서대로 찾을 수 있다. 이를 이용하면 중위 순회한 결과에서 흥미로운 결과를 얻을 수 있다.

예시에서 3,6,5,4,8,7,1,2과 5,6,8,4,3,1,2,7이 주어지는데 앞선 이해를 바탕으로 하면 3이 전체 트리의 루트이므로 중위 순회한 결과로부터 5,6,8,4는 좌측 서브트리이고 1,2,7은 우측 서브트리임을 알 수 있다.

그 다음 헤멘 곳은 전위 순회한 결과에서 다음 루트를 찾는 것이다. 좌측 서브트리 탐색은 연이어서 나오기 때문에 문제없이 찾을 수 있다. 하지만 좌측 서브트리 순회를 끝내고 우측 서브트리를 순회하고자 할 때 전위 순회한 결과에서 다음 루트를 찾는 것이 조금 어려웠다.

우측 서브트리 노드는 현재 있는 위치에서 좌측 서브트리의 크기만큼 떨어져있다.

다음과 같은 생각을 쉽게 할 수 있었다면 금방 풀었을텐데 그렇지 못했다. 코드에서 현재 있는 위치가 pos이고 좌측 서브트리의 크기는 i-s이다. i가 가리키고 있는 값이 서브트리의 루트이기 때문에 배열에서는 i-s로 볼 수 있다. 따라서 전위 순회할 결과에서 우측 순회를 위한 루트는 pos+i-s+1이 된다(ㅠㅠ).

이 부분을 이해했다면 나머지는 분할정복 방식으로 풀 수 있었다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;
int preorder(int* arr);
int indorder(int* arr);
int postorder(int start, int end, int pos);
int* preod;
int* inod;
int n;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int answer = 0;
	int t;

	cin >> t;
	for (int k = 0; k < t; k++) {
		
		cin >> n;
		preod = new int[n];
		inod = new int[n];

		for (int i = 0; i < n; i++) {
			cin >> preod[i];
		}

		for (int i = 0; i < n; i++) {
			cin >> inod[i];
		}
		postorder(0, n, 0);
		cout << '\n';
	}
}

int postorder(int s, int e, int pos) {
	for (int i = s; i < e; i++) {
		if (preod[pos] == inod[i]) {
			postorder(s,i,pos+1); //좌 서브트리 서칭
			postorder(i+1,e,pos+i-s+1); //우 서브트리 서칭
			cout << inod[i] << ' ';
		}
	}
	return 0;
}