4256 : 트리

풀이

어찌저찌 트리 다시 만들고 잘 짜면 된다.

풀이가 너무 부실한데?

다음의 예제를 보자.

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, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-09-17 12:21

Read more posts by this author