백준 2263 - 트리의 순회(C++)

문제

N개의 정점을 갖는 이진 트리의 정점에 1부터 N까지의 번호가 중복 없이 매겨져 있다.

 

이때 중위 순환과 후위 순환이 주어졌을 때, 선위 순환을 구하는 프로그램을 작성해라.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)

 

다음 줄에 중위 순환을 나타내는 N개의 자연수가 주어진다.

 

그다음 줄에 후위 순환을 나타내는 N개의 자연수가 주어진다.

 

예제 입력

3
1 2 3
1 3 2

 

예제 출력

2 1 3

 

문제 해결

어디서 힌트를 얻을 수 있을까?

 

우선 중위 순환과 후위 순환이 어떻게 이루어지는지 알 필요가 있다.

 

• 중위 순환 : (왼쪽)(루트)(오른쪽)
• 후위 순환 : (왼쪽)(오른쪽)(루트)
  
  

위를 보면 알겠지만 후위 순환으로 출력하게 될 경우 루트는 가장 마지막에 존재한다.

 

이를 통해 루트를 쉽게 찾을 수 있고 루트를 기준으로 '왼쪽'과 '오른쪽' 자식 노드들로 구분할 수 있다.

 

'왼쪽'과 '오른쪽' 두 키워드를 보면 이것을 루트를 기준으로 분할 할 수 있겠다라는 생각이 든다.

 

그럼 후위 순환을 통해 기준점인 루트를 찾아주고 중위 순환을 분할하여 찾아낸 루트를 순서대로 출력하면 우리가 찾고자 하는 선위 순환을 출력할 수 있게 된다.

 

• 선위 순환 : (루트)(왼쪽)(오른쪽)
  
  

중위 순환에서 루트를 찾는 것은 단순히 반복문을 통해 이룰 수 있지만 다음과 같이 세팅을 하면 상수 시간으로 찾을 수 있다.

int index[N];

index[inOrder[i]] = i;

이 코드는 찾고자 하는 해당 값이 몇 번째 인덱스인지 알려준다.

 

코드

#include <iostream>

int N;
int inOrder[100001];
int postOrder[100001];
int index[100001];

void solve(int inS, int inE, int poS, int poE, int size)
{
	if (inS > inE || poS > poE)
		return ;
	int root = index[postOrder[poE]];
	int left = root - inS;
	int right = inE - root;
	std::cout << inOrder[root] << ' ';

	solve(inS, root - 1, poS, poS + left - 1);
	solve(root + 1, inE, poS + left, poE - 1);
}

int main(void)
{
	std::cin >> N;
	for (int i = 1; i <= N; i++)
	{
		std::cin >> inOrder[i];
		index[inOrder[i]] = i;
	}
	for (int i = 1; i <= N; i++)
		std::cin >> postOrder[i];
	solve(1, N, 1, N, N);
	std::cout << std::endl;
	return 0;
}

문제 출처

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

2263번: 트리의 순회