BOJ 2263 트리의 순회

이진트리 순회에 대해 다시 한번 복습 할 수 있는 문제이다. 기본적으로 이진트리 순회 방법은 전위(pre), 중위(in), 후위(post)로 3가지 방법이 존재한다. 이 문제는 단순 이진트리 순회가 아닌 중위, 후위 순서가 주어지고 이를 이용하여 트리를 재구성 하는 문제이다. 

 

이진트리 순회 방법은 아래를 참고하자.

전위순회

루트 - 왼쪽 노드 - 오른쪽 노드

중위순회

왼쪽 노드 - 루트 - 오른쪽 노드

후위순회

왼쪽 노드 - 오른쪽 노드 - 루트

문제에서 입력은 중위 순서와 후휘 순서가 주어진다. 예를들어 입력이 다음과 같다고 가정해보자.

11
8 4 2 9 5 1 10 6 3 11 7 (중위)
8 4 9 5 2 10 6 11 7 3 1 (후위)

 

전위 순회를 하기위해서 각 레벨에서 루트를 찾는것이 핵심이다. 기본적으로 후위에서 가장 마지막으로 출력되는것이 루트가 된다. 풀이 방법은 기본적으로 전위 순회를 따라가면서 탐색할 후위 범위를 재조정 하는 것이다. 후위 탐색 구간이 재조정 될때마다 조정된 구간의 마지막 노드가 다음 레벨의 루트가 된다.

 

레벨0에서 구간은 1 ~ 11이 된다. 이 구간에서 레벨 0의 루트는 후위의 마지막 노드인 1이 된다.

이후 중위에서 1인 노드를 찾고 해당 노드를 기준으로 왼쪽, 오른쪽을 전위순회 방식을 이용하여 구간을 재정의 해준다.

 

레벨1에서 왼쪽 구간은 1 ~ 5가 되고 이 구간에서 후위의 마지막 노드는 2가 된다.

이후 중위에서 2인 노드를 찾고 해당 노드를 기준으로 왼쪽, 오른쪽을 전위순회 방식을 이용하여 구간을 재정의 해준다.

 

레벨1에서 오른쪽 구간은 7 ~ 10가 되고 이 구간에서 후위의 마지막 노드는 3가 된다.

이후 중위에서 3인 노드를 찾고 해당 노드를 기준으로 왼쪽, 오른쪽을 전위순회 방식을 이용하여 구간을 재정의 해준다.

 

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int In_Order[100001];
int Post_Order[100001];
int Pre_Order[100001];
int n;

int number(pair<int,int> a)
{
	int num = (a.second - a.first + 1);
	return num > 0?num:0;
}


void FindChildNode(pair<int,int> in, pair<int,int> post)
{
	int left_num = 0, right_num = 0;//왼쪽 자식과 오른쪽 자식 남은 갯수를 저장한다.
	pair<int, int> in_left, post_left, in_right, post_right;// 자식 노드 구간
	int mid = Post_Order[post.second];
	cout << mid << " ";

	in_left = in_right = in;
	in_left.second = In_Order[mid] - 1;// in order의 왼쪽 자식의 끝 
	in_right.first = In_Order[mid] + 1;//in order의 오른쪽 자식의 시작

	left_num = number(in_left); // in order의 왼쪽 자식의 갯수
	right_num = number(in_right);// in order의 오른쪽 자식의 갯수

	//이후 in order에 따른 post를 구해준다.

	if(left_num > 0)
	{
		post_left.second = post.second - 1 - right_num;
		post_left.first = post_left.second + 1 - left_num;
		FindChildNode(in_left, post_left);
	}
	if(right_num > 0)
	{
		post_right.second = post.second - 1;
		post_right.first = post.second - right_num;
		FindChildNode(in_right, post_right);
	}
}

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

	memset(In_Order, 0, sizeof(In_Order));
	memset(Post_Order, 0, sizeof(Post_Order));
	memset(Post_Order, 0, sizeof(Post_Order));

	cin >> n;

	for(int i = 1; i<= n; i++)
	{
		int num;
		cin >> num;
		In_Order[num] = i;// 위치를 담고있음
	}

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

	FindChildNode({ 1,n }, { 1,n });
}