백준 6597번 트리 복구

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

아래와 같은 두 성질을 이용하면 쉽게 풀 수 있는 문제였습니다.

1. 전위 탐색을 했을 때 제일 앞에 있는 노드가 해당 서브트리의 노드입니다.

2. 중위 탐색을 했을 때 루트를 기준으로 왼쪽에 나오는 노드들은 왼쪽 서브트리, 오른쪽에 나오는 노드들은 오른쪽 서브트리에 속한 노드들입니다.

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

 

void postOrder(string preOrder, string inOrder)

{

        //기저 사례

        if (!preOrder.length())

                 return;

 

        //트리에 포함된 노드의 수

        int num = preOrder.size();

        const char root = preOrder[0];

        //왼쪽 서브트리의 크기

        const int left = find(inOrder.begin(), inOrder.end(), root) - inOrder.begin();

        //오른쪽 서브트리의 크기

        const int right = num - left - 1;

        //왼쪽 서브트리

        postOrder(preOrder.substr(1, left), inOrder.substr(0, left));

        //오른쪽 서브트리

        postOrder(preOrder.substr(left + 1, num), inOrder.substr(left + 1, num));

 

        cout << root;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

 

        while(1)

        {

                 string preOrder, inOrder;

                 cin >> preOrder >> inOrder;

 

                 if (!preOrder.length())

                         break;

 

                 postOrder(preOrder, inOrder);

                 cout << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

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