트리 순회 순서 변경

https://algospot.com/judge/problem/read/TRAVERSAL

트리에 대한 기초적인 개념이 있는 상태에서 문제를 풀 수 있습니다.

혹시나 트리가 무엇인지 모르시면 

트리의 개념과 그 용어들을 살피고 오세요.

문제상에서 전위, 중위 순서의 순서가 먼저 주어지고 이를 통해 후위 탐색의 순서를 출력하는 문제입니다.

<출처 : https://algospot.com/judge/problem/read/TRAVERSAL>

탐색의 순서는 재귀적으로 해결할 수 있습니다.

하지만 트리가 주어지지 않은 상태에서는 어떻게 접근해야 할까요.

가령 27, 16, 54가 있다면 중위순회는 왼쪽-루트-오른쪽의 순서로 순회합니다.

즉, 루트가 어디에 있냐만 차이가 생기죠.

결국 어떤 트리의 전위순회 순서가 다음과 같이 주어진다면,

[A],[B],[C]

루트는 A입니다.

이를 토대로 중위 순회순서는 [B],[A],[C]가 됩니다.

후위 순회순서는 [A],[C],[B]가 됩니다.

이러한 개념을 가지고 문제를 풀어봅니다.

전위순회:27 16 9 12 54 36 72

중위순회:9 12 16 27 36 54 72

이 순서를 보고 루트가 무엇인지를 대번에 어떻게 알 수 있을까요.

바로 전위순회입니다. 전위 순회의 맨 처음이 루트이기 때문입니다.

다시 27을 가지고 중위 순회를 나눈겁니다.

다시말해 중위순회에서 27을 기준으로 왼쪽은 루트의 왼쪽 오른쪽 배열은 루트의 오른쪽노드들의 자식이 될 것이기 때문입니다.

이를 재귀적으로 풀어나가면 다음과 같은 코드를 만들 수 있습니다.

makePostOrder를 호출할 때 전처리 해서 생성된 pre, in을 매개변수로 입력합니다.

19번줄을 기준으로 left와 right를 만들어내고, 마지막에 root를 post에 입력합니다.

후위순회는 왼쪽,오른쪽,루트를 순서대로 방문하니까요

gettingVectorFromValue 함수는 위의 설명처럼 27을 기준으로 나누기 위한 함수입니다.

책에 있는것이 더 효율적이겠으나 제 코드를 그대로 올립니다 ^^;