[C++] 백준 4256 : 트리

https://www.acmicpc.net/problem/4256

4256번: 트리

 

 

inorder & preorder 두 정보를 가지고 postorder 나타내기

이전 문제:https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

와 동일한 문제인데 얘는 inorder&postorder 가지고 preorder 나타내는 문제

 

잘 이해했나 확인하려고 비슷한거 더 풀어봄

 

해결하기

근데 문제에서

라는 말이 있는데 그러면 두 순회 결과로 유일한 이진 트리가 만들어지지 않는 경우도 있나? 하고 궁금해짐....

어떻게 그러지?

 

근데 개인적으로

https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

이 문제랑 크게 다르지 않은데..

골드5랑 골드2라서 좀 신기하다 ㅋㅋ 비슷한거 같은데

#include <iostream>

int preorder[1000];
int inorder[1000];

void postorder(int s1, int e1, int s2, int e2) {
	if (s1 > e1 || s2 > e2) return;

	int root = preorder[s1];
	int left_len = 0;
	for (int i = s2; i <= e2; i++) {
		if (inorder[i] == root) {
			break;
		}
		left_len++;
	}
	
	//left
	postorder(s1 + 1, s1 + left_len, s2, s2 + left_len - 1);
	//right
	postorder(s1 + left_len + 1, e1, s2 + left_len + 1, e2);
	printf("%d ", root);
}

int main() {
	int TC;
	scanf("%d", &TC);
	while (TC--) {
		int N;
		scanf("%d", &N);

		for (int i = 0; i < N; i++) {
			scanf("%d", &preorder[i]);
		}

		for (int i = 0; i < N; i++) {
			scanf("%d", &inorder[i]);
		}

		postorder(0, N - 1, 0, N - 1);
		printf("\n");
	}
}