Algospot Traversal

array의 start, end 포인트만을 사용한 풀이

// TRAVERSAL

int preTree[N_MAX];
int inTree[N_MAX];
int postTree[N_MAX];

void guessPostTree(int preS, int preE, int inS, int inE, int postS, int postE)
{
    if (postS > postE)  return;

    // Initial Case
    int root;
    for (root = inS; root <= inE; root++){
        if (preTree[preS] == inTree[root])
            break;
    }   
    postTree[postE] = inTree[root];

    // Recursive
    int leftLen = root - inS;
    guessPostTree(preS + 1, preS + leftLen, inS, root - 1, postS, postS + leftLen - 1); // Left
    guessPostTree(preS + leftLen + 1, preE, root + 1, inE, postS + leftLen, postE - 1); // Right

    cout << inTree[root] << " ";
}

int main()
{
    int T, N, i, j;
    cin >> T;
    for (int tc = 0; tc < T; tc++){
        cin >> N;
        for (i = 0; i < N; i++) cin >> preTree[i];
        for (i = 0; i < N; i++) cin >> inTree[i];

        vector<int> v1(preTree, preTree + N);
        vector<int> v2(inTree, inTree + N);

        guessPostTree(0, N - 1, 0, N - 1, 0, N - 1);
        cout << endl;
    }
    return 0;
}

slice()를 이용한 깔끔한 vector를 주고 받는 풀이

vector<int> slice(const vector<int>& v, int a, int b){
    return vector<int>(v.begin() + a, v.begin() + b);
}

void guessPostTree(const vector<int>& preorder, const vector<int>& inorder)
{
    // 00. exit condition
    if (preorder.empty())   return;

    // 01. find the root and the pos of the root
    int N = preorder.size();
    int root = preorder[0];
    int leftLen = find(inorder.begin(), inorder.end(), root) - inorder.begin();

    // 02. print the left & right trees, then the root
    guessPostTree(slice(preorder, 1, leftLen + 1), slice(inorder, 0, leftLen));     // left sub-tree
    guessPostTree(slice(preorder, leftLen + 1, N), slice(inorder, leftLen + 1, N)); // right sub-tree
    cout << root << " ";
}

int main()
{
    int T, N, i, j;
    cin >> T;
    for (int tc = 0; tc < T; tc++){
        cin >> N;
        for (i = 0; i < N; i++) cin >> preTree[i];
        for (i = 0; i < N; i++) cin >> inTree[i];

        vector<int> v1(preTree, preTree + N);
        vector<int> v2(inTree, inTree + N);

        guessPostTree(v1, v2);
        cout << endl;
    }
    return 0;
}