[백준] 5639 이진 검색 트리

트리 구조는 해당 노드의 값을 idx로 하고 [idx][0]에 왼쪽 노드를, [idx][1]에 오른쪽 노드를 넣어줬다.

노드를 하나씩 입력 받으면서 현재 부모인 노드와 크기를 비교하면서 적절히 트리 배치를 해준다!

이때, 현재 부모인 노드보다 현재 입력 받은 노드의 크기가 작다면 pre-order 입력 이므로 왼쪽 값을 계속해서 출력하고 있는 것이기 때문에 왼쪽에 현재 노드를 달아주고 다음 부모를 현재 입력 받은 노드로 바꿔준다.

만약 부모 노드보다 현재 입력 받은 노드의 크기가 크다면 이때까지 있던 root 중에서 현재 노드보다 작은 root중 upper_bound를 찾아준다!!! 그러고 그 노드의 오른쪽에 현재 노드를 달아주고 다음 부모를 현재 입력 받은 노드로 바꾼다!!

이렇게 해서 만들어진 tree 구조를 post-order로 돌아서 답을 출력한다!

 

#include <iostream>
#include <vector>
using namespace std;
int tree[1000001][2];
int n, max_node = 0;
vector<int> root_list;
void make_node(int num)
{
    if (num < root_list.back())
        tree[root_list.back()][0] = num;
    else
    {
        max_node = 0;
        for (int i = root_list.size() - 1; i >= 0; i--)
        {
            if (num < root_list[i])
                break;
            if (root_list[i] > max_node)
                max_node = root_list[i];
        }
        tree[max_node][1] = num;
    }
    root_list.push_back(num);
}
void postorder(int num)
{
    if (tree[num][0])
        postorder(tree[num][0]);
    if (tree[num][1])
        postorder(tree[num][1]);
    printf("%d\n", num);
}
int main()
{
    int cur_idx = 0;
    cin >> n;
    root_list.push_back(n);
    while (true)
    {
        cin >> n;
        if (cin.eof() == true)
            break;
        make_node(n);
    }
    postorder(root_list[0]);
}

 

Uploaded by Notion2Tistory v1.1.0