BOJ 2263 트리의 순회

1 개요

BOJ 2263 트리의 순회

• 백준 온라인 저지 2263번 문제
• BOJ 35단계

2 C++

#include <iostream>
using namespace std;

int n;
int A[100001];
int inorder[100001];
int postorder[100001];

void solve(int inStart, int inEnd, int postStart, int postEnd) {
    if (inStart > inEnd || postStart > postEnd) {
        return;
    }
    int rootIndex = A[postorder[postEnd]];
    int leftSize = rootIndex - inStart;
    int rightSize = inEnd - rootIndex;
    cout << inorder[rootIndex] << ' ';
    solve(inStart, rootIndex - 1, postStart, postStart + leftSize - 1);
    solve(rootIndex + 1, inEnd, postStart + leftSize, postEnd - 1);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> inorder[i];
        A[inorder[i]] = i;
    }
    for (int i = 1; i <= n; i++) {
        cin >> postorder[i];
    }
    solve(1, n, 1, n);
}