[트리] TRAVERSAL 트리 순회 순서 변경

1. 트리의 순회

이 문제는 트리의 preorder와 inorder가 주어졌을 때 이 정보를 가지고 postorder을 생성하는 문제이다.

 

preorder는 각 서브트리의 루트를 먼저 출력한다.

따라서 preord[0]은 이 트리의 루트가된다.

 

inorder는 서브트리의 왼쪽끝쪽을 조사한다음 서브트리의 루트를 출력한다음 오른쪽을 조사한다.

즉, 트리의 루트가 출력될때 이미 이 루트의 왼쪽 부분은 탐색을 마친 상태이다.

트리의 루트의 오른쪽은 오른쪽 서브 트리이다.

 

위의 각 순회의 특성을 이용하여 재귀적으로 함수를 구현하면 답을 쉽게 얻을 수 있다.

 

이 코드의 시간복잡도는 r 과 for문에 지배된다

for문은 각 단계에서 대략 n번 수행되고 r = n이므로

O(N^2)의 시간 복잡도를 가진다.

#include <iostream>
#include <vector>
 
using namespace std;
 
int testCase;
int N;
vector<int> preord;
vector<int> inord;
 
void decode(int i, int j, int& r)
{
    if(i == j) return;
 
    int root = preord[r++];
    int rootIndex;
 
    for(int k = i; k < j; k++)
        if(inord[k] == root)
            rootIndex = k;
 
    decode(i, rootIndex, r);
    decode(rootIndex + 1, j, r);
 
    cout<<root<<" ";
}
 
int main()
{
    cin>>testCase;
    for(int i = 0 ; i < testCase; i++)
    {
        int r = 0;
        cin>>N;
        preord.resize(N);
        inord.resize(N);
        for(int j = 0 ; j < N; j++)
            cin>>preord[j];
        for(int j = 0; j < N; j++)
            cin>>inord[j];
        decode(0, N, r);
        cout<<"\n";
    }
}

TRAVERSAL