[백준 4256번] 트리

문제 링크: www.acmicpc.net/problem/4256

4256번: 트리

<문제 풀이> DFS(깊이 우선 탐색), 트리

전위 순회 결과 3 6 5 4 8 7 1 2 

중위 순회 결과 5 6 8 4 3 1 2 7

중위 순회 결과를 통해서 각 노드의 순서를 알 수 있고, 왼쪽 서브 트리와 오른쪽 서브 트리에 어떤 노드가 존재하는지 알 수 있습니다.

그리고 전위 순회 결과를 통해 규칙을 찾아볼 수 있는데, 크기가 n인 배열에 전위 순회 결과가 차례로 저장돼 있다고 했을 때 인덱스 + 1을 하면 왼쪽 서브 트리의 루트를 가리키게 할 수 있습니다.

예를 들어 arr [] = {3 ,6, 5, 4, 8, 7, 1, 2]인 배열이 있습니다. 이때

root == 3, index = 0 되고, 왼쪽 서브 트리로 이동하면

root == 6, index = 1 이 됩니다.

 

그리고 오른쪽 서브트리로 이동하는 방법은 왼쪽 서브 트리의 크기 + 1 만큼 인덱스를 더해주면 됩니다.

 

root == 3, index = 0

root == 7, index = 0 + 4 + 1 == 5

 

 

 

<C++ 소스 코드>

#include <iostream>
#include <vector>
using namespace std;
 
int preorder[1001];
int inorder[1001];
 
 
void solution(int root, int s, int e){
    for(int i = s ; i < e; i++){
        if(inorder[i] == preorder[root]){
            solution(root + 1, s, i); // left sub tree
            solution(root + i + 1 - s, i + 1, e); // right sub tree
            cout<<preorder[root]<<" ";
        }
    }
}
 
int main(void) {
    int test_case; 
    cin>>test_case;
    while(test_case--){
        int n ; cin>>n;
        for(int i=0; i<n; i++){
            cin >> preorder[i];
        }
        for(int i=0; i<n; i++){
            cin >> inorder[i];
        }
        solution(0, 0, n);
        cout<<'\n';
    }
    return 0;
}