[백준] 2263번: 트리의 순회 (c++)

 

문제

---

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오.

2263번: 트리의 순회

 

문제조건

---

1≤n≤100,000

 

풀이

---

 

인오더와 포스트오더를 구해보면 포스트 오더의 가장 마지막 값이 루트 값임을 알 수 있다. 인오더는 루트값을 기준으로 왼쪽과 오른쪽으로 나뉜다. 인오더를 통해 오른쪽과 왼쪽으로 나눈 후, 포스트오더에서 이 값들의 가장 마지막 값을 보면 루트 값을 알 수 있다.

 

코드

---

#include <iostream>
#include <vector>
 
using namespace std;
 
int inorder[100001];
int postorder[100001];
int idx[100001];
 
void preOrder(int inStart, int inEnd, int postStart, int postEnd)
{
    // 더 이상 분할 할 수 없는 경우 return
    if (inStart > inEnd || postStart > postEnd)
        return;
 
    // postorder의 끝 값이 root값
    int rootIndex = idx[postorder[postEnd]];
    int leftSize = rootIndex - inStart;
    int rightSize = inEnd - rootIndex;
 
    // root 출력
    cout << inorder[rootIndex] << ' ';
 
    //왼쪽
    preOrder(inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
    
    //오른쪽
    preOrder(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
}
 
 
int main() {
	int n;
 
	cin >> n;
 
	for (int i = 0; i < n; i++) {
		cin >> inorder[i];
	}
 
	for (int i = 0; i < n; i++) {
		cin >> postorder[i];
	}
 
	for (int i = 0; i < n; i++) {
		idx[inorder[i]] = i;
	}
 
    preOrder(0, n-1, 0, n-1);
}