[BOJ] 4256 트리 C++

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

4256번: 트리

이진트리에서 전위순회와 중위 순회가 주어졌을 때, 후위 순회를 구하는 문제이다. 저번에 후위 순회와 중위 순회가 주어졌을 때 전위 순회를 구하는 문제를 풀어서 쉽게 풀 수 있었다.

https://coderecord.tistory.com/5

[BOJ] 2263 트리의 순회 C++

위 글과 비교했을 때, 인자 값만 바뀌었으므로 위 글을 참조하면 된다.

 

코드

#include <iostream>
using namespace std;
int T,N;
int preorder[1000];
int inorder[1000];

void find_postorder(int in_start,int in_end,int pre_start, int pre_end){
    if(in_start>in_end||pre_start>pre_end) return;
    int mid_idx;
    for(int i=in_start;i<=in_end;i++){
        if(preorder[pre_start]==inorder[i]){
            mid_idx=i;
            break;
        }
    }
    find_postorder(in_start,mid_idx-1,pre_start+1,pre_start-in_start+mid_idx);
    find_postorder(mid_idx+1,in_end,pre_start-in_start+mid_idx+1,pre_end);
    cout<<inorder[mid_idx]<<" ";
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>T;
    while(T--){
        cin>>N;
        for(int i=0;i<N;i++) cin>>preorder[i];
        for(int i=0;i<N;i++) cin>>inorder[i];
        find_postorder(0,N-1,0,N-1);
        cout<<'\n';
    }
    return 0;
}