[백준] 2263 트리의 순회

백준 2263 트리의 순회

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

• 이진 트리의 중위 순회 결과값(인오더)과 후위 순회 결과값(포스트오더)가 주어졌을 때,
  전위 순회 결과값(프리오더) 구하기

삽질 기록 1

• left Child의 inorder, postorder, preorder 와 right Child의 inorder, postorder, preorder 를 구하여 모두 각각의 벡터에 저장
  -> 전체 preorder 벡터의 뒤에 삽입하여 반환하는 함수 구현

• 메모리 초과
  -> 모든 순회의 결과값을 다 저장하는 풀이는 노드의 수가 클 경우 메모리 초과가 발생한다

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

vector<int> get(vector<int> inorder, vector<int> postorder) {

	//base case
	if (postorder.empty() || postorder.size() == 1)
		return postorder;
	
	//postorder: leftChild + rightChild + ROOT
	int rootVal = postorder.back();
	postorder.pop_back();

	auto rootIt = find(inorder.begin(), inorder.end(), rootVal);

	//leftChild
	//inorder
	vector<int> leftChildInorder;
	vector<int> leftChildPostorder;
	if (rootIt != inorder.begin()) {
		leftChildInorder.assign(inorder.begin(), rootIt);
		leftChildPostorder.assign(postorder.begin(), postorder.begin() + leftChildInorder.size());
	}
	vector<int> leftChildPreorder = get(leftChildInorder, leftChildPostorder);

	//rightChild
	vector<int> rightChildInorder;
	vector<int> rightChildPostorder;
	if (rootIt != inorder.end() - 1) {
		rightChildInorder.assign(rootIt + 1, inorder.end());
		rightChildPostorder.assign(postorder.begin() + leftChildInorder.size(), postorder.end());
	}
	vector<int> rightChildPreorder = get(rightChildInorder, rightChildPostorder);

	//preorder : ROOT + leftChild + rightChild
	vector<int> preorder;
	preorder.push_back(rootVal);
	preorder.insert(preorder.end(), leftChildPreorder.begin(), leftChildPreorder.end());
	preorder.insert(preorder.end(), rightChildPreorder.begin(), rightChildPreorder.end());
	return preorder;
}


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

	vector<int> inorder;
	vector<int> postorder;
	vector<int> preorder;

	int n;
	cin >> n;

	int input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		inorder.push_back(input);
	}
	for (int i = 0; i < n; ++i) {
		cin >> input;
		postorder.push_back(input);
	}

	preorder = get(inorder, postorder);
	
	for (auto it = preorder.begin(); it != preorder.end(); it++)
		cout << *it << " ";

	return 0;
}

삽질 기록 2

• 메모리를 줄여보고자 inorder, postorder는 인덱스를 이용해여 접근하고,
  left Child의 preorder과 right Child의 preorder 를 구하여 벡터에 저장
  -> 전체 preorder 벡터의 뒤에 삽입하여 반환하는 함수 구현

• 시간 초과
  -> 벡터의 assign()과 insert() 과정에서 시간을 많이 소요하기 때문에 노드의 수가 클 경우 시간 초과가 발생한다

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


vector<int> inorder;
vector<int> postorder;

vector<int> get(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {
	vector<int> preorder;

	//base case
	if (inorderStart == inorderEnd) {
		preorder.push_back(inorder[inorderStart]);
		return preorder;
	}

	//postorder: leftChild + rightChild + ROOT
	int root = postorder[postorderEnd];

	auto inorderRootIt = find(inorder.begin() + inorderStart, inorder.begin() + inorderEnd, root);
	int inorderRoot = inorderRootIt - inorder.begin();

	//leftChild
	vector<int> leftChildPreorder;
	if(inorderRoot != inorderStart)
		leftChildPreorder = get(inorderStart, inorderRoot - 1, postorderStart, postorderStart + (inorderRoot -1 - inorderStart));

	//rightChild
	vector<int> rightChildPreorder;
	if (inorderRoot != inorderEnd) 
		rightChildPreorder = get(inorderRoot + 1, inorderEnd, postorderStart + (inorderRoot - 1 - inorderStart) + 1, postorderEnd - 1);

	//preorder : ROOT + leftChild + rightChild
	preorder.push_back(root);
	preorder.insert(preorder.end(), leftChildPreorder.begin(), leftChildPreorder.end());
	preorder.insert(preorder.end(), rightChildPreorder.begin(), rightChildPreorder.end());
	return preorder;
}


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

	int n;
	cin >> n;

	int input;
	for (int i = 0; i < n; ++i) {
		cin >> input;
		inorder.push_back(input);
	}
	for (int i = 0; i < n; ++i) {
		cin >> input;
		postorder.push_back(input);
	}

	vector<int> preorder = get(0, n-1,0, n-1);

	for (auto it = preorder.begin(); it != preorder.end(); it++)
		cout << *it << " ";

	return 0;
}

풀이

• 벡터에 저장/삽입하는 과정을 전부 빼고 preorder 결과값을 출력만 하는 반환값이 없는 함수로 다시 구현

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

int inorder[100001] = { 0 };
int postorder[100001] = { 0 };

void preorder(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {
	
	//base case
	if (inorderStart == inorderEnd) {
		cout<< inorder[inorderStart] <<" ";
		return;
	}

	//postorder: leftChild + rightChild + ROOT
	int root = postorder[postorderEnd];
	int inorderRoot = 0;
	for (int i = inorderStart; i <= inorderEnd; ++i) {
		if (inorder[i] == root) {
			inorderRoot = i;
			break;
		}
	}

	//preorder : ROOT + leftChild + rightChild
	cout << root << " ";
	//leftChild
	if (inorderRoot != inorderStart)
		preorder(inorderStart, inorderRoot - 1, postorderStart, postorderStart + (inorderRoot - 1 - inorderStart));
	//rightChild
	if (inorderRoot != inorderEnd)
		preorder(inorderRoot + 1, inorderEnd, postorderStart + (inorderRoot - 1 - inorderStart) + 1, postorderEnd - 1);

	return;
}


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

	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) 
		cin >> inorder[i];
	for (int i = 0; i < n; ++i)
		cin >> postorder[i];

	preorder(0, n - 1, 0, n - 1);
	return 0;
}

더 빠른 풀이

• 풀이 : 메모리 7884KB, 시간 1212ms
  더 빠른 풀이: 메모리 7232KB, 시간 28ms

• inorder값의 인덱스를 저장하는 배열 inorder_index를 선언
  -> inorder에서의 root의 인덱스를 구할 때, inorder_index$[$root$]$값을 이용

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

int inorder_index[100001] = { 0 };

int inorder[100001] = { 0 };
int postorder[100001] = { 0 };

void preorder(int inorderStart, int inorderEnd, int postorderStart, int postorderEnd) {
	
	//base case
	if (inorderStart == inorderEnd) {
		cout<< inorder[inorderStart] <<" ";
		return;
	}

	//postorder: leftChild + rightChild + ROOT
	int root = postorder[postorderEnd];
	int inorderRoot = inorder_index[root];

	//preorder : ROOT + leftChild + rightChild
	cout << root << " ";
	//leftChild
	if (inorderRoot != inorderStart)
		preorder(inorderStart, inorderRoot - 1, postorderStart, postorderStart + (inorderRoot - 1 - inorderStart));
	//rightChild
	if (inorderRoot != inorderEnd)
		preorder(inorderRoot + 1, inorderEnd, postorderStart + (inorderRoot - 1 - inorderStart) + 1, postorderEnd - 1);

	return;
}


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

	int n;
	cin >> n;

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

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

	preorder(0, n - 1, 0, n - 1);
	return 0;
}

📌참고자료

• 백준 2263 트리의 순회 풀이
  https://donggoolosori.github.io/2020/10/15/boj-2263/