[백준 4256 C++][G4] 트리

⭐️ 난이도

Gold 4

---

⭐️ 문제

https://www.acmicpc.net/problem/4256

4256번: 트리

각 테스트 케이스마다 이진 트리의 전위 순회, 중위 순회의 결과가 주어진다.

이때, 이진 트리의 후위 순회의 결과를 구하시오.

 

---

⭐️ Idea flow

 

문제에서 전위 순회(preorder)과 중위 순회(inorder)의 결과가 주어진다.

전위 순회를 root 노드를 먼저 방문하는 방법이고, 중위 순회는 root 노드를 중간에 방문하는 방법이다.

이와 같은 특성을 잘 이용해야 하는 문제이다.

 

전체적인 알고리즘

1) 전위 순회는 루트 노드를 제일 먼저 방문하기 때문에 루트 노드가 제일 앞에 위치한다.

2) 루트 노드를 얻었으므로 중위 순회에서 루트 노드를 기준으로

   왼쪽에 있는 수들은 left subtree, 오른쪽에 있는 수들은 right subtree이다.

   여기서 left subtree의 크기를 알 수 있다.

3) 얻은 left subtree 크기 만큼 전위 순회에서 index를 옮긴다면, right subtree에 포함되는 수들이 나온다.

   전위 순회 배열(preorder)과 중위 순회 배열(inorder)의 범위를 조절하여 매개 변수로 전달한다.

   여기에서도 루트 노드가 제일 앞에 위치한다.

4) 위와 같은 방법을 반복한다.

 

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <unordered_set>
#include <unordered_map>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 4256 - 트리
vector<int> preorder, inorder;
vector<int> idx;


void input(int& n){
    cin >> n;
    preorder.assign(n + 1, 0);
    inorder.assign(n + 1, 0);
    idx.assign(n + 1, 0);

    for(int i = 1; i <= n; i++){
        cin >> preorder[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> inorder[i];
        idx[inorder[i]] = i; // 몇 번째 인덱스에 있는지 저장
    }
}

void get_postorder(int pre_start, int pre_end, int in_start, int in_end){
    if(pre_start > pre_end || in_start > in_end)    return;

    int root_num = preorder[pre_start]; // 전위 순회는 루트 노드가 제일 앞에 위치
    int root_idx = idx[root_num]; // 루트 노드가 inorder 배열에서 몇 번째에 위치하는지 확인
    int left_size = root_idx - in_start; // 왼쪽 서브 트리의 크기가 얼마나 되는지 확인

    // search left subtree
    get_postorder(pre_start + 1, pre_start + left_size, in_start, root_idx - 1);
    // search right subtree
    get_postorder(pre_start + left_size + 1, pre_end, root_idx + 1, in_end);
    cout << root_num << ' ';
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int testcase = 0;
    cin >> testcase;

    while(testcase--){
        int n = 0;
        input(n);
        get_postorder(1, n, 1, n);

        cout << '\n';
    }

    return 0;
}

 

---

⭐️ Feedback

 

preorder, inorder, postorder의 특성에 대해 더 자세히 생각해볼 수 있는 문제였다.

 

preorder는 루트 노드를 먼저 방문하므로 제일 앞의 인덱스에서 루트 노드를 얻을 수 있다.

inorder는 루트 노드를 중간에 방문하므로, 루트 노드의 인덱스를 알고 있다면 left subtree와 right subtree를 구할 수 있다.