[백준 2263번] 트리의 순회(C++)

아이디어

post의 가장 오른쪽 원소를 inorder에서 찾아서 나누면서 분할 정복.

 

C++풀이

#include <bits/stdc++.h>
using namespace std;
int n;
int inorder[100001];
int postorder[100001];
void solve(pair<int,int> idx_in, pair<int,int> idx_post)
{
    int post_left = idx_post.first;
    int post_right = idx_post.second;
    int in_left = idx_in.first;
    int in_right = idx_in.second;
    cout <<postorder[post_right]<< " ";
    if(in_left == in_right || post_left == post_right ) {
        return;
    }

    //인덱스 찾아주기.
    int mid_left;
    int mid_right;
    for(int i=in_left; i<=in_right; i++)
    {
        if(inorder[i] == postorder[post_right])
        {
            mid_left = i-1;
            mid_right = i+1;
        }
    }
    //left먼저
    if(mid_left>=0 && in_left <=mid_left) 
    	solve({in_left,mid_left},{post_left,post_left+(mid_left-in_left)});

    //right index넘겨주기
    if(mid_right <=n-1 && mid_right <=in_right) 
    	solve({mid_right,in_right},{post_right-(in_right-mid_right+1),post_right-1});
    
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    //input setting
    for(int i = 0 ; i< 2; i++)
    {
        for(int j= 0; j< n ; j++)
        {
            int temp;
            cin >> temp;
            // inorder input
            if(i== 0)
            {  
                inorder[j]=temp;
            }
            // postorder input
            else
            {
                postorder[j] = temp;
            }
        }
    }
    solve({0,n-1},{0,n-1});

}