백준 2263번 트리의 순회

문제 링크입니다: https://www.acmicpc.net/problem/2263

직접 트리를 그려본 다음에 유도를 해보는 것이 제일 적절한 해법인 것 같습니다.

후위 순회를 기준으로 생각해보면 맨 마지막에 위치한 노드가 해당 트리의 루트입니다.

그리고 중위 순회를 기준으로 생각해보면 루트가 나오기 전까지는 왼쪽 부분트리이고 나온 후에는 오른쪽 부분트리입니다.

따라서, 이 성질을 이용해서 재귀함수를 호출하면 AC를 받을 수 있습니다.

#include <iostream>

using namespace std;

 

const int MAX = 100000 + 1;

 

int inOrder[MAX], postOrder[MAX];

int idx[MAX];

 

void preOrder(int inBegin, int inEnd, int postBegin, int postEnd)

{

        //모순

        if (inBegin > inEnd || postBegin > postEnd)

                 return;

 

        int root = postOrder[postEnd];

        cout << root << " ";

        //왼쪽

        preOrder(inBegin, idx[root] - 1, postBegin, postBegin + (idx[root] - inBegin) - 1);

        //오른쪽

        preOrder(idx[root] + 1, inEnd, postBegin + (idx[root] - inBegin), postEnd - 1);

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int N;

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> inOrder[i];

        for (int i = 0; i < N; i++)

                 cin >> postOrder[i];

 

        for (int i = 0; i < N; i++)

                 idx[inOrder[i]] = i;

 

        preOrder(0, N - 1, 0, N - 1);

        cout << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~