[In-Order,Pre-Order]
1.in-Order에 대한 알고리즘은 다음과 같다.
1.LeftNode Search ->CurrentNode Processing ->RightNode Search
2.Post-Order에 대한 알고리즘은 다음과 같다.
1.LeftNode Search ->RightNode Search ->CurrentNode Processing
다음과 같은 이진 트리가 있다.
[그림1]
Processing을 현재 노드 번호의 출력이라고 하자.
in-Order는 다음과 같다.
2->4->3->1->6->9->8->5->7->10
Post-Oder는 다음과 같다.
4->3->2->9->8->6->10->7->5->1
[추론]
In-Order의 정보와 Post-Order의 정보를 바탕으로 트리를 구축하여야한다.
추론(1): Post-Order는 루트에 해당하는 노드는 자식들이 전부 출력된후 항상 맨 마지막에 출력된다.
예를들어 Post-Order의 1번 노드는 해당하는 left자식들과 Right자식들이 모두 출력된후 출력된다.
추론(2): In-Order는 경우 범위 내에서 루트 노드를 기준으로 왼쪽 출력은 왼쪽 자식노드들이고 오른쪽 출력은 오른쪽 자식노드들이다.
예를들어 in-Order에서 1번 노드 왼쪽에 출력된 2->4->3->1은 1의 왼쪽에 위치해있다. 오른쪽에 있는 6->9->8->5->7->10은 오른쪽에 있는 자식들이다.
추론(3): Post-Order의 경우 출력에 있어서 루트를 기준으로 왼쪽이 전부출력된후 오른쪽이 전부출력되고 그후 루트가 출력이된다.
예를들어 7->5->1에서 5가 1번의 오른쪽노드이다.
그렇다면 이를 바탕으로 문제를 해결해보자
[알고리즘]
1. 추론(1)에 따라서 현재 범위내의 루트노드를 찾는다. 그리고 출력한다.
2. 1에서 찾은 RootNode를 가지고 추론(2)를 이용하여 Inorder에서 LeftNode의 갯수와 RightNode의 갯수를 파악하자.
3. 2번 에서 파악한 왼쪽 및 오른쪽 자식의 갯수를 가지고 추론(3)을 따라서 왼쪽과,오른쪽 범위를 새롭게 지정해준후 다시 (1~3)을 반복한다.
[시뮬레이션]
[그림1]에 해당하는 In-Order,Post-Order에서 알고리즘대로 진행해보자.
초기조건:
Post-Order의 범위:[1-10]
In-Order의 범위:[1-10]
in-Order:
2->4->3->1->6->9->8->5->7->10
Post-Oder:
4->3->2->9->8->6->10->7->5->1실행:
1.Post-Order에서 루트노드찾기: 1출력
2.루트노드를 기반으로 범위내의 자식갯수파악하기: 왼쪽자식 3개** 오른쪽자식 6개
in-Order:
2->4->3->1->6->9->8->5->7->10
Post-Oder:
4->3->2->9->8->6->10->7->5->1
3.이후 범위 새롭게 지정해주기
왼쪽자식의 In-Order범위:[1~3], Post-Order범위:[1~3]
오른쪽자식의 In-Order범위:[5~10],Post-Order범위:[4~9]
4.3번에서 찾은 왼쪽 자식,오른쪽 자식을 1번부터 다시진행
.
.
.
.
[코드]
#include <bits/stdc++.h>
using namespace std;
#define MaxSize 100001
#define f(i, j, k) for (int i = j; i <= k; i++)
#define range pair<int, int>
#define start first
#define end second
int N;
int In_Order[MaxSize];
int Post_Order[MaxSize];
int number(range A) {
int num = (A.end - A.start + 1);
return num > 0 ? num : 0;
}
//현재까지 탐색한 InOrder의 범위를 가지고있어야함
//현재까지 탐색한 PostOrder의 범위도 가지고 있어야함.
//in_range,post_range 두개변수
//1.먼저 post_range안의 맨마지막 수A를 찾음 출력
//2.inOrder안에 A의 순서를 찾음
//3.in_range안의 A의 왼쪽과 오른쪽의 갯수를 찾음
//4.오른쪽갯수가 존재할경우 해당범위 재지정및 1~4,(오른쪽갯수+1)왼쪽출력(1~4)
void FindChildNode(range in_range, range post_range)
{
int left_num = 0, right_num = 0;
range in_left, in_right, post_left, post_right;
in_left = in_right = in_range;
int mid = Post_Order[post_range.end];
cout << mid << " ";
in_left.end = In_Order[mid] - 1;
in_right.start = In_Order[mid] + 1;
left_num = number(in_left);
right_num = number(in_right);
if (left_num > 0)
{
post_left.end = post_range.end - 1 - right_num, post_left.start = post_left.end + 1 - left_num;
FindChildNode(in_left, post_left);
}
if (right_num > 0)
{
post_right.end = post_range.end-1, post_right.start = post_range.end - right_num;
FindChildNode(in_right, post_right);
}
}
int main(void)
{ /*
10
2 4 3 1 6 9 8 5 7 10
4 3 2 9 8 6 10 7 5 1
*/
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> N;
f(i, 1, N)
{
int k;
cin >> k;
In_Order[k] = i; //위치를담고있다.
}
f(i, 1, N) cin >> Post_Order[i];
FindChildNode({ 1,N }, { 1,N });
return 0;
}