[백준] #4325 트리🌲

• 백준 #4325 트리
• 사용언어 : C++
• 문제 등급 : 골드 Ⅲ 🥇

문제

• 예시
  

어떠한 트리를 전위, 중위 순회한 결과가 각각 주어지고, 이를 이용해 트리를 후위 순회한 결과를 구하는 문제이다.

분석

주어진 예시를 분석해보자.

• 전위 순회 : 3 6 5 4 8 7 1 2
• 중위 순회 : 5 6 8 4 3 1 2 7

1. 전위 순회 결과의 처음 값 = 3 = 루트 노드

2. 중위 순회 결과에서 3을 기준으로 left tree와 right tree가 나뉨 : 5 6 8 4 3 1 2 7

3. 전위 순회 결과의 두번째 값 = 6 = left tree의 루트 노드

4. 2에서 구한 left tree에서 , 6 을 기준으로 left tree의 left , right가 나뉨 : 5 6 8 4

   ...반복...

루트 노드를 기준으로 left , right 트리가 분리되고,
left , right 트리에서 다시 각각의 루트 노드를 찾는 과정이 반복되는 것을 알 수 있다.

🧙‍♂️ 분석 결과
동일한 연산이 반복 - 재귀
트리의 크기가 점점 작아짐 - divide and conquer

구현화

트리 표현

• 중위 순회의 인덱스 범위로 표현
• 예시 : 5 6 8 4 3 1 2 7 - left tree : (0, 3)
  
  

재귀 함수(first, last)

3 6 5 4 8 7 1 2
5 6 8 4 3 1 2 7

1. base : if (first > last) → return
2. 전위 순회에서 노드 하나씩 갖고옴 (맨앞에서부터)
3. 트리에서 노드의 위치 찾기(인덱스 찾기)
4. 인덱스 기준으로 트리를 left, right로 나눈 후 재귀
   • 재귀함수(first, 인덱스 -1)
   • 재귀함수(인덱스 +1, last)
5. 노드 출력
   
   

예시
(0,7) → 트리에서 3의 인덱스 : 4 → (0,3) , (5,7) → 3 출력

코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int T,N;
int i, j;
int cur;
queue<int> preorder;
vector<int> inorder;

void init();
void printPostorder(int first, int last);

int main()
{
 
    cin >> T;   
    for(i=0;i<T;i++){
      
        init();
        
        for(j=0;j<N;j++){
            cin >> cur;
            preorder.push(cur);
        }
        for(j=0;j<N;j++){
            cin >> cur;
            inorder.push_back(cur);
        }
        
        printPostorder(0,N-1);
        cout << "\n";
    }

    return 0;
}

void init(){
    inorder.clear();
    cin >>N;
}

void printPostorder(int first, int last){
    if(first > last)
        return;
    
		//find root index
    auto begin = inorder.begin();
    auto end = inorder.end();
    auto root = preorder.front();
    preorder.pop();
    
    int rootIdx = distance(begin, find(begin,end,root));
    
    printPostorder(first,rootIdx-1) ;  // left tree
    printPostorder(rootIdx+1,last) ;   // right tree
    
    cout << root <<" ";
    
}

느낀 점

역시 재귀에 관한 문제는 base와 재귀부분만 설정을 잘하면 간단히 해결된다는 것을 느낄 수 있었다.
요 근래 스터디에서 재귀 문제를 주로 풀었더니 기존에 재귀에 대해 가지고 있던 혼란스러움이 어느 정도 해결되는 것 같아 뿌듯하다.