21장 트리 순회 순서 변경 TRAVERSAL

#include<iostream>
#include<string>
#include<vector>
#include<cassert>
#include<algorithm>
#include<queue>
#include<functional>
#include<random>
using namespace std;
 
vector<int> slice(const vector<int>& v, int a, int b) {
    return vector<int>(v.begin() + a, v.begin() + b);
}
//트리의 전위탐색 결과와 중위탐색 결과가 주어질 때 후위탐색 결과를 출력한다.
void printPostOrder(const vector<int>& preorder, const vector<int>& inorder) {
    //트리에 포함된 노드의 수
    const int N = preorder.size();
    //기저 사례: 텅 빈 트리면 곧장 종료
    if (preorder.empty()) return;
    //이 트리의 루트는 전위 탐색 결과로부터 곧장 알 수 있다.
    const int root = preorder[0];
    //이 트리의 왼쪽 서버트리의 크기는 중위 탐색 결과에서 루트의 위치를 찾아서 알수 있다.
    //find 함수는 포인터값을 반환하기 때문에 -inorder.begin() 즉 시작 주소를 빼줘야 위치를 알 수가 있다.
    const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();
 
    //오른쪽 서브트리의 크기는 N에서 왼쪽 서브트리와 루트를 빼면 알 수 있다.
    const int R = N - 1 - L;
    //왼쪽과 오른쪽 서브트리의 순회 결과를 출력
    printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
    printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
    //후위 순회이므로 루트를 가장 마지막에 출력한다.
    cout << root << ' ';
}
 
 
int main(void){
    int cases;
    cin >> cases;
    while(cases--)
    {
        int N;
        cin >> N;
        vector<int> pre, in;
        for (int i = 0; i < N; i++) {
            int a;
            cin >> a;
            pre.push_back(a);
        }
        for (int i = 0; i < N; i++) {
            int a;
            cin >> a;
            in.push_back(a);
        }
        printPostOrder(pre, in);
        cout << endl;
    }
    return 0;
}

문제 출처:https://algospot.com/judge/problem/read/TRAVERSAL

재귀함수를 사용하는 법이 아직 많이 미숙하네요. 

문제를 푸는 포인트는 두가지입니다.

1.preorder의 시작은 root(preorder[0])이다.

2.inorder의 값이 root와 일치하기전 까지가 왼쪽 서브트리의 구성원소들이다.

string.find함수와 헷갈려서 find함수는 포인터값을 반환한다는 걸 몰라서 코드를 봤을떄 -inorder.begin()을 보고 당황했었습니다.ㅎㅎ

헷갈리지않도록 주의해야겠어요.

+vector의 끝은 열려있으므로 slice함수를 사용할때도 자르기원하는 위치+1을 해주는 것도 주의하자!

 //위치를 이렇게 변경하면 L(왼쪽) V(방문) R(오른쪽)순으로 중위 순회가 된다.
 printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
 cout << root << ' ';
 printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));
 
//위치를 이렇게 변경하면 V(방문) L(왼쪽) R(오른쪽) 순으로 전위 순회가 된다.
 cout << root << ' ';
 printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));
 printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));