[Algorithm] 2263: 트리의 순회

📦2263: 트리의 순회

---

[알고리즘 풀이] 강동규
Reviewed by Kade Kang (devkade12@gmail.com)
Reviewed:: 2024-02-20
문제 확인하기

풀이

• Preorder : 루트 - 왼쪽 - 오른쪽
• Inorder : 왼쪽 - 루트 - 오른쪽
• Postorder : 왼쪽 - 오른쪽 - 루트
• 따라서, Postorder의 맨마지막 출력은 Preorder의 루트 노드가 된다.
• 그리고, 위 성질을 이용해서 각 부분 별로 왼쪽과 오른쪽의 루트를 재귀적으로 구해나간다.
• 즉, Inorder의 경우 왼쪽, 오른쪽의 기준을 잡기 위해 필요하고 Postorder는 루트를 구하기 위해 필요하다.

#include <iostream>
 
#define endl '\n'
using namespace std;
 
int n;
int preorder[100001];
int inorder[100001];
int postorder[100001];
 
void Input(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> inorder[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> postorder[i];
    }
}
 
void Solution(int begin1, int end1, int begin2, int end2){
    if(begin1 > end1 && begin1 > end2) return;
    int root = postorder[end2];
 
    int flag = -1;
    for(int i=begin1; i <= end1; i++){
        if(inorder[i]==root) {
            flag = i;
            break;
        }
    }
    int len = flag - begin1;
 
    cout << root << ' ';
    Solution(begin1, flag-1, begin2, begin2+len-1);
    Solution(flag+1, end1, begin2+len, end2-1);
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    Input();
    Solution(1, n, 1, n);
 
    return 0;
}