[백준/BOJ] 백준 2263번 : 트리의 순회

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

2263번: 트리의 순회

 

입력받은 중위 순회(인오더)와 후위 순회(포스트오더)에서 같은 부분을 나타내는 인덱스의 범위를 표현하여, 같은 부분의 후위 순회의 범위는 range_post_left ~ range_post_right, 중위 순회의 범위는 range_in_left ~ range_in_right로 확인하며, 후위 순회의 마지막은 루트 노드라는 점을 이용하여, 전위 순회(프리오더)의 값을 채우고 해당 노드 왼쪽을 확인하고 다음으로 해당 노드 오른쪽을 확인하는 방법으로 문제를 해결했다.

 

코드

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

int n;
int number_in_order[100005]; //[숫자]=중위순회에서 위치

vector<int> in_order;
vector<int> post_order;
vector<int> result;

void solve(int range_post_left, int range_post_right, int range_in_left, int range_in_right) {

	//범위가 잘못 되었을때
	if (range_post_left > range_post_right || range_in_left > range_in_right) {
		return;
	}

	int root = post_order[range_post_right]; //후위순회의 마지막은 루트노드
	result.push_back(root);

	int root_in_order_index = number_in_order[root]; //루트노드의 중위순회에서의 위치
	int left_cnt = root_in_order_index - range_in_left; //루트노드의 왼쪽 자식 서브트리의 노드 개수
	int right_cnt = range_in_right - root_in_order_index; //루트노드의 오른쪽 자식 서브트리의 노드 개수

	//root를 기준으로 왼쪽 확인
	solve(range_post_left, range_post_left + left_cnt - 1, range_in_left, root_in_order_index - 1);

	//root를 기준으로 오른쪽 확인
	solve(range_post_left + left_cnt, range_post_right - 1, root_in_order_index + 1, range_in_right);
}

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		in_order.push_back(input);
		number_in_order[input] = i;
	}

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		post_order.push_back(input);
	}

	solve(0, n - 1, 0, n - 1);

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << " ";
	}

	return 0;
}