백준
백준 소스코드 [C++] 2263 트리의 순회
Hani_Levenshtein
2021. 3. 1. 00:58
2263번: 트리의 순회
첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다.
www.acmicpc.net
백준 소스코드 [C++] 2263 트리의 순회
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>
#include <limits.h>
#include <vector>
#include <math.h>
#include <stack>
#include <bitset>
#include <string>
#include <set>
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
typedef long long ll;
using namespace std;
vector<int> idx,post,in;
void preorder(int postL, int postR, int inL, int inR) {
if (postR < postL || inR < inL) return;
cout << post[postR] << " ";
preorder(postL, postL+idx[post[postR]]-inL-1,inL, idx[post[postR]] - 1);
preorder(postL + idx[post[postR]] - inL, postR-1, idx[post[postR]] +1,inR);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
idx.resize(n+1); post.resize(n+1); in.resize(n+1);
for (int i = 1;i <= n;i++) {
cin >> in[i];
idx[in[i]] = i;
}
for (int i = 1;i <= n;i++) cin >> post[i];
preorder(1,n,1,n);
return 0;
}