백준 2263 - 트리의 순회

문제링크

• 백준 2263

문제설명

• n개의 정점을 갖는 이진 트리가 1부터 n까지 번호가 매겨져 있다.
• 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하라

입력

• n(10만 이하)
• 인오더를 나타내는 n개의 자연수
• 포스트오더를 나타내는 n개의 자연수

문제접근방향

• Postorder의 마지막 원소는 트리의 root가 된다.
• Inorder는 root를 중심으로 왼쪽이 Left tree, 오른쪽이 right tree가 된다.
  1. Postorder 배열에서 마지막 원소를 root로 선정한다.
  2. Inorder에서 root를 찾고, 왼쪽 배열과 동일한 원소를 갖도록 Postorder 배열에서 찾아 해당 배열로 배열을 파싱한다.
  • 인덱스로 파싱.
  • inorder 배열에서 root의 인덱스-1이 left tree의 마지막 인덱스가 된다. 3. 선정된 root는 출력하고, 1번으로 돌아가는 로직을 재귀적으로 구현한다.
  • 재귀호출마다 분할된 배열에 대해 일관적인 인덱싱이 이루어져야 한다. 이번 경우에서는 배열의 시작부분, 끝부분이 주어지고 이 영역에서 구한 root 인덱스 정보가 해당 영역에서만 유효한 데이터이다. 이 데이터를 가지고 해당 영역 안에서 Left, Right 영역을 나누어주어야 한다.

구현 (런타임 에러)

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

// inorder의 root 인덱스를 반환한다.
// 매개변수 start, end를 모두 포함하는 범위를 탐색한다.
int find_root_inorder(vector<int>&inorder, int start, int end, int root) {
	for (int idx = start; idx <= end; idx++) {
		if (root == inorder[idx])
			return idx;
	}
}

void find_preorder(vector<int>& inorder, vector<int>& postorder, int p_start_idx, int p_end_idx, int i_start_idx, int i_end_idx) {
	// root 출력
	cout << postorder[p_end_idx] << " ";
	// 기저사례: postorder 구간 길이가 1인 경우
	if (i_start_idx == i_end_idx) return;

	// index 정리
	int i_root_idx = find_root_inorder(inorder, i_start_idx, i_end_idx, postorder[p_end_idx]);
	int i_left_start_idx = i_start_idx;
	int i_left_end_idx = i_root_idx - 1;
	int left_size = i_left_end_idx - i_left_start_idx + 1;

	int i_right_start_idx = i_root_idx + 1;
	int i_right_end_idx = i_end_idx;
	int right_size = i_right_end_idx - i_right_start_idx + 1;

	int p_left_start_idx = p_start_idx;
	int p_left_end_idx = p_left_start_idx + left_size - 1;
	int p_right_start_idx = p_left_end_idx + 1;
	int p_right_end_idx = p_end_idx - 1;

	// Left tree
	find_preorder(inorder, postorder, p_left_start_idx, p_left_end_idx, i_left_start_idx, i_left_end_idx);
	// Right tree
	find_preorder(inorder, postorder, p_right_start_idx, p_right_end_idx, i_right_start_idx, i_right_end_idx);

	return;
}

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

	int n;
	cin >> n;
	vector<int> inorder(n,0);
	vector<int> postorder(n,0);

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

	find_preorder(inorder, postorder, 0, n - 1, 0, n - 1);
	return 0;
}

원인분석

• 다양한 경우를 시도해보던 중 아래 그림처럼 왼쪽 자식노드가 없고 오른쪽 자식노드만 있는 경우 메모리 초과가 발생하는 것을 확인하였다.
• 이진트리가 자식 노드를 하나만 가지고 있을 때 문제가 된다.

       1
    2      3
  4   5  6   7
   9 8

# 입력
9
4 9 2 8 5 1 6 3 7
9 4 8 5 2 6 7 3 1

# 정답
1 2 4 9 5 8 3 6 7 

• 9를 출력하지 못하고 런타임에러 발생

구현(Pass)

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

// inorder의 root 인덱스를 반환한다.
// 매개변수 start, end를 모두 포함하는 범위를 탐색한다.
int find_root_inorder(vector<int>&inorder, int start, int end, int root) {
	for (int idx = start; idx <= end; idx++) {
		if (root == inorder[idx])
			return idx;
	}
}

void find_preorder(vector<int>& inorder, vector<int>& postorder, int p_start_idx, int p_end_idx, int i_start_idx, int i_end_idx) {
	// root 출력
	cout << postorder[p_end_idx] << " ";
	// 기저사례: postorder 구간 길이가 1인 경우
	if (i_start_idx == i_end_idx) return;

	// index 정리
	int i_root_idx = find_root_inorder(inorder, i_start_idx, i_end_idx, postorder[p_end_idx]);
	int i_left_start_idx = i_start_idx;
	int i_left_end_idx = i_root_idx - 1;
	int left_size = i_left_end_idx - i_left_start_idx + 1;

	int i_right_start_idx = i_root_idx + 1;
	int i_right_end_idx = i_end_idx;
	int right_size = i_right_end_idx - i_right_start_idx + 1;

	int p_left_start_idx = p_start_idx;
	int p_left_end_idx = p_left_start_idx + left_size - 1;
	int p_right_start_idx = p_left_end_idx + 1;
	int p_right_end_idx = p_end_idx - 1;

    // 왼쪽 자식, 오른쪽 자식이 존재하면 재귀호출을 한다.
	// Left tree
	if(left_size>0)
		find_preorder(inorder, postorder, p_left_start_idx, p_left_end_idx, i_left_start_idx, i_left_end_idx);
	// Right tree
	if(right_size>0)
		find_preorder(inorder, postorder, p_right_start_idx, p_right_end_idx, i_right_start_idx, i_right_end_idx);

	return;
}

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

	int n;
	cin >> n;
	vector<int> inorder(n,0);
	vector<int> postorder(n,0);

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

	find_preorder(inorder, postorder, 0, n - 1, 0, n - 1);
	return 0;
}