문제 이해 단계
https://www.acmicpc.net/problem/2263
이진트리의 정점이 1~n까지의 번호가 중복 없이 매겨져 있다.
이진트리의 중위 순회와 후위 순회가 입력으로 주어질 때,
전위 순회를 출력하는 문제
문제 접근 단계
전위, 중위, 후위 순회의 개념과 특성을 미리 알고 있어야 한다.
전위 순회 : 루트 → 왼쪽 → 오른쪽
중위 순회 : 왼쪽 → 루트 → 오른쪽
후위 순회 : 왼쪽 → 오른쪽 → 루트
그림을 보면서 하는 것이 가장 빠르다.
중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6
후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0
이 된다.
우리는 이 2가지 정보를 가지고 전위 순회를 구해야 한다.
일단 후위 순회는 루트 노드가 마지막에 오기 때문에,
즉 0번 노드가 루트노드이다.
중위 순회는 왼쪽 -> 루트 -> 오른쪽이다.
그래서 루트 노드를 알고 있다면
루트 노드를 기준으로 왼쪽, 오른쪽 서브 트리를 나눌 수 있다.
중위나, 후위나 왼쪽이나 오른쪽의 서브트리 개수는 같다.
즉, 개수를 통해 후위 쪽에서 왼쪽 서브트리에서의 루트와
오른쪽 서브트리의 루트를 구할 수 있다.
그림으로 나타내면 다음과 같다.
또다시 이런 식으로 소분된다.
이 행위를 반복하면 되기 때문에, 재귀함수를 통해 이 문제를 해결하면 된다.
매개변수로 중위노드의 왼쪽과 오른쪽,
후위 노드의 왼쪽과 오른쪽을 받아서 반복한다.
자세한 것은 문제 구현 단계에서 보겠다.
문제 구현 단계
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> in; // 중위 순회
vector<int> post; // 후위순회
int n;
void preorder(int pLeft, int pRight, int iLeft ,int iRight){
// 왼쪽 포인터가 오른쪽보다 커지면 종료
if(pLeft > pRight || iLeft > iRight) return;
int root = post[pRight]; // 해당 후위 순회의 마지막 노드가 루트임
int in_root;
cout << root << " ";
// 루트에 매치하는 노드를 중위 순회에서 찾음
for(int i = iLeft; i <= iRight; i++){
if(in[i] == root){
in_root = i;
break;
}
}
// 왼쪽 노드의 개수
int left = in_root - iLeft;
preorder(pLeft,pLeft+left-1,iLeft,in_root-1); // 왼쪽 노드로 재귀함수 호출
preorder(pLeft+left,pRight-1,in_root+1,iRight); // 오른쪽 노드로 재귀함수 호출
}
int main(){
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
cin >> n;
in.resize(n);
post.resize(n);
for(int i = 0; i < n; i++) cin >> in[i];
for(int i = 0; i < n; i++) cin >> post[i];
int start = post.size()-1;
preorder(0,in.size()-1,0,post.size()-1);
}pLeft와 pRight는 후위 순회의 왼쪽포인터와 오른쪽 포인터이고,
iLeft와 iRight는 중위 순회의 왼쪽포인터와 오른쪽 포인터이다.
그리고 중위순회에서 그 값을 빼서 개수를 찾고,
그 노드들로 다시 재귀함수를 호출한다.
핵심적인 설명은 여기까지이다.
시행착오
이진 트리에 관한 개념이 있어야만 풀 수 있는 문제여서
좀 힘들었기도 했고, 많이 생소했던 문제였다.
다음에 나오면 틀리지 말아야지.
생활비..