[ 백준 4256 ] 트리 (c/c++)

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

 

 

[ 문제 요약 ]

테스트 게이스 T, 노드의 개수 N이 주어지고 트리를 전위 순회한 결과와 중위 순회한 결과가 주어질 때, 후위 순회한 결과를 출력한다.

 

 

[ 문제 풀이 ]

1. 전위 순회의 첫번째 노드는 무조건 루트 노드이다.

2. 중위 순회에서 특정 노드보다 앞에 있는 노드는 왼쪽의 서브 트리에 존재하고 오른쪽에 있는 노드는 오른쪽의 서브 트리에 존재한다.

3. 중위 순회에서 왼쪽 서브 트리에 존재하는 인덱스라면 전위 순회에서도 왼쪽 서브 트리에 존재한다.

4. 위 특성들을 가지고 왼쪽, 오른쪽으로 나누어서 재귀함수를 돌리면 답을 출력할 수 있다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int T, N, a;
vector<int> fv;
vector<int> mv;

void Find(int s, int e, int n){
    for (int i=s; i<e; i++){
        if (mv[i] == fv[n]){
            Find(s, i, n + 1);
            Find(i+1, e, n + 1 + i - s);
            cout << fv[n] << " ";
        }
    }
}

int main() {
    cin >> T;
    while (T--){
        cin >> N;
        fv.clear();
        mv.clear();
        for (int i=0; i<N; i++){
            cin >> a;
            fv.push_back(a);
        }
        for (int i=0; i<N; i++){
            cin >> a;
            mv.push_back(a);
        }
        Find(0, N, 0);
        cout << "\n";
    }
    return 0;
}

 

 

 

[ 주의할 점 ]

전위 순회와 중위 순회 간의 특성을 생각해서 문제를 풀어야 한다.