Boj2263_트리의 순회

Published: December 04, 2018 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

boj2263_트리의 순회

#include<iostream>
using namespace std;
int in_num[100001], post_num[100001];
int in_order[100001], post_order[100001];
int n,num;

void go(int s, int e,int s1, int e1) {//in
	if (s == e) {
		printf("%d ", in_order[s]);
		return;
	}
	else if (s > e) { return; }
	int my_in_order_index = in_num[post_order[e1]];

	//나
	go(my_in_order_index, my_in_order_index,e1,e1);
	//왼
	int last_post_left_idx = s1 + (my_in_order_index-1 - s);
	go(s,my_in_order_index-1,s1,last_post_left_idx);
	//오
	go(my_in_order_index+1,e,last_post_left_idx+1,e1-1);
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &in_order[i]);
		in_num[in_order[i]] = i;
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &post_order[i]);
		post_num[post_order[i]] = i;
	}
	go(0, n - 1,0,n-1);
}