풀이
어찌저찌 트리 다시 만들고 잘 짜면 된다.
풀이가 너무 부실한데?
다음의 예제를 보자.
8
3 6 5 4 8 7 1 2
5 6 8 4 3 1 2 7
예를 들어, 지금 inorder로 3을 보고 있다면
preorder 기준으로 3을 반으로 나누면 5 6 8 4, 1 2 7이 있다.
이 말은 노드3에 대해, 5 6 8 4는 왼쪽, 1 2 7은 오른쪽 서브트리 노드들이라는 뜻이다.
이제 이를 토대로 쭉 짜보자.
코드
#include <cstdio>
#include <iostream>
using namespace std;
class Node {
public:
int value;
Node *left, *right;
Node(int value):value(value) {}
};
int n;
int order[1001];
int preorder[1001];
int inorder[1001];
Node* make_tree(int st, int ed) {
if (st > ed)
return NULL;
int min_order = 0x7ffffff, min_value = 0, min_i = 0;
for (int i = st; i <= ed; i++) {
int value = inorder[i];
if (min_order > order[value]) {
min_order = order[value];
min_value = value;
min_i = i;
}
}
Node *root = new Node(min_value);
root->left = make_tree(st, min_i - 1);
root->right = make_tree(min_i + 1, ed);
return root;
}
void post_order(Node *node) {
if (node->left != NULL) post_order(node->left);
if (node->right != NULL) post_order(node->right);
printf("%d ", node->value);
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> preorder[i];
order[preorder[i]] = i + 1;
}
for (int i = 0; i < n; i++) {
cin >> inorder[i];
}
Node *root = make_tree(0, n - 1);
post_order(root);
printf("\n");
}
}
/*
2
4
3 2 1 4
2 3 4 1
8
3 6 5 4 8 7 1 2
5 6 8 4 3 1 2 7
*/
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이