[백준/BOJ] 백준 4256번 : 트리

www.acmicpc.net/problem/4256

4256번: 트리

전위 순회의 첫 번째가 해당 트리(서브 트리)의 루트 노드라는 것을 구할 수 있고, 구한 루트 노드를 이용해, 중위 순회 결과에서 해당 트리(서브 트리)의 왼쪽 부분의 노드 개수를 구할 수 있다. 이를 통해 해당 트리(서브 트리)를 왼쪽 부분, 오른쪽 부분으로 나눌 수 있다.

 

코드

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

int t;
int n;
vector<int> preorder;
vector<int> inorder;

void Pre()
{
	preorder.clear();
	inorder.clear();
}


vector<int> Solve(int pre_front, int pre_back, int in_front, int in_back)
{
	vector<int> ret;

	if (pre_front > pre_back || in_front > in_back)
		return ret;

	//전위 순회의 첫번째가 해당 서브트리의 루트노드
	int root = preorder[pre_front];

	//노드가 하나만 있을때
	if (pre_front == pre_back && in_front == in_back)
	{
		ret.push_back(root);

		return ret;
	}

	//중위 순회 결과를 통해 왼쪽 서브트리의 노드 개수를 구한다
	int front_cnt = 0;
	for (int i = in_front; i <= in_back; i++)
	{
		if (inorder[i] == root)
		{
			break;
		}

		else
		{
			front_cnt++;
		}
	}

	vector<int> result1 = Solve(pre_front + 1, pre_front + 1 + front_cnt - 1, in_front, in_front + front_cnt - 1);
	vector<int> result2 = Solve(pre_front + 1 + front_cnt, pre_back, in_front + front_cnt + 1, in_back);
	int result3 = root;

	for (int i = 0; i < result1.size(); i++)
		ret.push_back(result1[i]);
	for (int i = 0; i < result2.size(); i++)
		ret.push_back(result2[i]);
	ret.push_back(result3);

	return ret;
}

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

	cin >> t;

	for (int tc = 0; tc < t; tc++)
	{
		Pre();

		cin >> n;

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

			preorder.push_back(input);
		}

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

			inorder.push_back(input);
		}

		vector<int> result = Solve(0, n - 1, 0, n - 1);

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

	}



	return 0;
}