[백준 C++] 2263 트리의 순회 - 트리

2263번: 트리의 순회

---

 

문제풀이

 

중위 순회와 후위 순회 노드 순서가 주어졌을 때 전위 순회 노드 순서를 출력하는 문제입니다.

후위 순회의 맨 뒷 노드를 루트 노드로 지정할 때,

해당 루트 노드를 기준으로 중위 순회 정보에서 양 옆을 쪼개서 재귀 함수를 호출하도록 구현했습니다.

 

다음은 예시입니다.

 

 

중위 순회: 14 5 10 1 16 7 13 3 9 11 2 6 15 4 12 8

후위 순회: 14 10 7 16 1 5 3 13 11 2 4 8 12 15 6 (9)

 

이런 모양의 트리가 주어졌을 때,

후위 순회의 맨 뒷 노드(9)가 첫 루트 노드임을 알 수 있습니다.

해당 루트 노드를 출력하고 중위 순회에서 루트 노드를 기준으로 양 옆을 쪼개줍니다.

 

중위 순회: (14 5 10 1 16 7 13 3) (9) (11 2 6 15 4 12 8)

후위 순회: 14 10 7 16 1 5 3 13 11 2 4 8 12 15 6 (9)

 

쪼개진 중위 순회의 왼쪽 자식 그룹과 오른쪽 자식 그룹의 인덱스 정보를 이용해서

후위 순회도 두 그룹으로 쪼개줍니다.

 

중위 순회: (14 5 10 1 16 7 13 3) (9) (11 2 6 15 4 12 8)

후위 순회: (14 10 7 16 1 5 3 13) (11 2 4 8 12 15 6) (9)

 

그 다음 중위 순회의 왼쪽 자식 시작 인덱스(LIS), 끝 인덱스(LIE),

후위 순회의 왼쪽 자식 시작 인덱스(LPS), 끝 인덱스(LPE)를 파라미터로 재귀함수를 호출해줍니다.

그리고 오른쪽 자식도 마찬가지로 네 개의 매개변수(RIS, RIE, RPS, RPE)를 재귀로 넘겨주어 호출합니다.

 

이 과정을 반복합니다.

---

코드

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

int N;
int IO[100001];
int PO[100001];

void Recursive(int IS, int IE, int PS, int PE)
{
	int Root = PO[PE];
	cout << Root << ' ';
	if (PS == PE)
	{
		return;
	}

	int IRIdx = find(IO + IS, IO + IE + 1, Root) - IO;
	int LeftNum = IRIdx - IS;
	int RightNum = IE - IRIdx;

	int RF = IO[IRIdx + 1];
	int PRFIdx = find(PO + PS, PO + PE + 1, RF) - PO;
	if (PE - PRFIdx < RightNum)
	{
		PRFIdx -= RightNum - (PE - PRFIdx);
	}

	if (PRFIdx - 1 >= PS && PRFIdx - 1 < PE)
	{
		Recursive(IS, IRIdx - 1, PS, PRFIdx - 1);
	}

	if (PRFIdx >= PS && PRFIdx < PE)
	{
		Recursive(IRIdx + 1, IE, PRFIdx, PE - 1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N;
	
	for (int i = 0; i < N; ++i)
	{
		cin >> IO[i];
	}

	for (int i = 0; i < N; ++i)
	{
		cin >> PO[i];
	}

	Recursive(0, N - 1, 0, N - 1);
}